[BOJ][백준 1038] 감소하는 수 - C++

 

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

백준 사이트의 1038번 문제, 감소하는 수 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

길이가 짧은 문제는 항상 좋다.

• N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다.
• 한 칸에는 물고기가 최대 1마리 존재한다.
• 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  -> 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
  -> 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기      를 먹는다.

K개의 CCTV가 설치되어 있고, CCTV는 총 5가지 종류이다.

• 1번 CCTV는 한 쪽 방향만 감시할 수 있다.
• 2번은 감시하는 방향이 서로 반대방향인 두 방향이다.
• 3번은 직각 방향인 두 방향이다.
• 4번은 세 방향을 감시할 수 있다.
• 5번은 네 방향을 감시할 수 있다.

• 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

---

1. 문제풀이 아이디어

• 아기 상어의 위치부터 퍼져나가는 BFS알고리즘을 구현한다.
• 만약 자기보다 몸집 큰 물고기 만나면 continue.
• 먹을 수 있는 물고기를 만나면 우선순위에 따라 먹을 물고기를 정해준다.
• 그 위치부터 다시 다음 BFS알고리즘 시작!
• 현재까지 먹은 물고기 수를 계산하여 아기상어 사이즈를 갱신한다.
• 더 이상 먹을 물고기가 없다면 결과 출력

---

2. 코드 핵심 부분

1) DFS를 이용하여 감소하는 수를 생성하는 함수,

   일단 순서는 나중에 정렬을 통해 따지고 일단 경우를 다 담았다.

// DFS를 이용하여 감소하는 수를 생성하는 함수
void dfs(int prev) {
    int temp = 0; // 감소하는 수를 임시로 저장할 변수
    int Len = Path.size(); // 현재까지 생성된 감소하는 수의 길이

    // 감소하는 수를 정수로 변환하여 temp에 저장한다.
    for (int i = 0; i < Len; i++) {
        temp *= 10;
        temp += Path[i];
    }

    v.push_back(temp); // temp를 벡터에 저장한다.

    // 이전에 생성된 감소하는 수보다 작은 숫자들을 이용하여 감소하는 수를 생성한다.
    for (int i = 0; i < prev; i++) {
        Path.push_back(i);
        dfs(i);
        Path.pop_back();
    }
}

 

2) 출력 처리 함수,

   sort 함수를 통해 이때 오름차순으로 수들을 정렬해준것을 볼 수 있다.

   정렬이 딱 한번만 필요하기 때문에 우선순위 큐가 아닌 정렬을 사용하였다.

   그리고 9876543210은 따로 빼준것을 볼 수 있는데,

   마지막 감소하는 수인 이 수는 int형으로 담을수가 없다....

   그래서 어쩔 수 없이 하드코딩이 들어갔는데 자료형을 바꿔준다면 이 부분은 필요없을 것이다.

// 출력 처리 함수
void output() {
    int Size = v.size(); // 생성된 감소하는 수의 개수

    if (N >= Size) { // N이 감소하는 수의 개수를 초과하는 경우 -1 출력
        cout << -1;
    }
    else if (N == Size - 1) { // N이 감소하는 수의 개수와 같은 경우 최대 감소하는 수인 9876543210 출력
        cout << 9876543210;
    }
    else { // 그 외에는 벡터를 정렬하여 N번째로 작은 감소하는 수 출력
        sort(v.begin(), v.end());
        cout << v[N];
    }
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

/*
1. 문제 요약
- 백준 1038번 문제: 감소하는 수
- 0부터 9까지의 숫자로 이루어진 감소하는 수를 N번째로 작은 수를 구하는 문제
*/

/*
2. 구현 아이디어
- DFS(깊이 우선 탐색)를 이용하여 감소하는 수를 생성하고, 생성된 수를 벡터에 저장한다.
- 생성된 벡터를 정렬하여 N번째로 작은 감소하는 수를 출력한다.
- N이 감소하는 수의 개수를 초과하는 경우 -1을 출력한다.
*/

// 필요 인자들
int N;
vector<int> v; // 감소하는 수를 저장할 벡터
vector<int> Path; // DFS에서 생성되는 감소하는 수를 임시로 저장할 벡터

// 입력 처리 함수
void input() {
    cin >> N;
    v.push_back(0); // 0을 벡터에 미리 저장해둔다.
}

// DFS를 이용하여 감소하는 수를 생성하는 함수
void dfs(int prev) {
    int temp = 0; // 감소하는 수를 임시로 저장할 변수
    int Len = Path.size(); // 현재까지 생성된 감소하는 수의 길이

    // 감소하는 수를 정수로 변환하여 temp에 저장한다.
    for (int i = 0; i < Len; i++) {
        temp *= 10;
        temp += Path[i];
    }

    v.push_back(temp); // temp를 벡터에 저장한다.

    // 이전에 생성된 감소하는 수보다 작은 숫자들을 이용하여 감소하는 수를 생성한다.
    for (int i = 0; i < prev; i++) {
        Path.push_back(i);
        dfs(i);
        Path.pop_back();
    }
}

// 출력 처리 함수
void output() {
    int Size = v.size(); // 생성된 감소하는 수의 개수

    if (N >= Size) { // N이 감소하는 수의 개수를 초과하는 경우 -1 출력
        cout << -1;
    }
    else if (N == Size - 1) { // N이 감소하는 수의 개수와 같은 경우 최대 감소하는 수인 9876543210 출력
        cout << 9876543210;
    }
    else { // 그 외에는 벡터를 정렬하여 N번째로 작은 감소하는 수 출력
        sort(v.begin(), v.end());
        cout << v[N];
    }
}

// 메인함수
int main() {
    // 입력 처리
    input();

    // 감소하는 수 생성
    for (int i = 1; i <= 9; i++) {
        Path.push_back(i);
        dfs(i);
        Path.pop_back();
    }

    // 출력 처리
    output();

    return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과... 오버플로우에 당해버린 모습

 

처음에는 탐색 문제가 아니라 수학 문제라고 생각했다.

 

그래서 감소하는 수가 나타나는 규칙성으로 문제를 풀려고 했는데

잘 되지않아 다시 설계를 해보니 이런

 

그냥 브루트포스 알고리즘 문제였다...

수가 커서 시간 초과가 무서웠는데 이걸 백트래킹만 잘한다면

실행시간은 그렇게 걸리지 않는다.

 

그리고 자료형 항상 조심할 것.

마지막 숫자는 워낙 커서 int형으로 담을 수가 없다.

 

어렵지 않은 문제인데 왜 이 정답률인가 했더니

함정이 상당히 많은 문제였다.