백준 1039 - 교환 (안보이는 DFS, BFS)

교환 

 

시간 제한    메모리 제한

2 초

128 MB

 

문제

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

 

---

1. 문제 해석

- N이라는 숫자를 자릿수를 K번 바꾸어서 만들 수 있는 가장 큰 수를 찾는 것이다. 

 

문제접근을 할 때 처음엔 손으로 풀어보았다. K=1일때  12345라면 52341로, 11113이라면 31111로 바뀐다. 

대충 앞자리수가 가장 크면 큰 수가 되니, 이렇게 바꾸면 되겠다 싶었다.

다만 이미 가장 큰 숫자 형태인데 또 연산을 해야할 때는 맨 뒤의 두자리를 바꿔주자!라고 생각했다. 

 

여기서 간과한 점 첫번째는, 수 내부에 중복되는 숫자가 있을 경우, 가장 큰 수에 도달했을 때 중복되는 숫자끼리 바꿔준 셈치면 된다는 점이었다.

 

이렇게 간단하게 풀릴 문제가 아님에도, 내가 생각한 모든 예시가 들어맞았기 때문에, 바로 채점을 했고, 

바로 틀려버렸다. 

 

 

게시판에서 예시들을 찾다가 찾은 나를 괴롭히던 반례는 바로, '7899, 2'였다.

 

애초에  내가 짠 코드는 K번 연산할 때, 한번 연산 시에 가장 큰 숫자로 바꾸게끔 하는 코드였다. 

이 논리에 따르면 7899는 1번째는 9879가 되고, 두번째에 가장 큰 수가 되려면 9978이 된다. 

 

하지만 실제로 2번연산시에 가장 커질 수 있는 경우는 7899 -> 7989 -> 9987이다.

 

여기서 내가 깨달은 것의 핵심은, 내가 아무생각없이 짠 코드는 전체문제를 부문제로 쪼개어, 부문제를 풀다보면 전체 해에 도달한다는 논리에 의한 코드, 특히 그리디한 코드였는데, 이게 맞는 해에 도달할지에 대한 검증이 부족했다는 것이었다.

 

왜 매번 가장 큰 수가 되게끔 선택해야 K번째 연산 시에 가장 큰 수에 도달할 수 있는 걸까?

-> 원래는 직감상 이렇게 되면 될거라 생각했으나, 

-> 반례 7899를 찾아버렸고, 

-> 이 경우를 커버하기 위해선 도무지 그리디하게 풀 방법이 없다는 걸 깨달았다. 

-> 이걸 알기 전에 검증하려고 했다면, 글쎄, 못했을 것 같기는 하다. 

   (매번 마음에 담아두고 있는 연습하고 싶은 것이 그리디를 풀기 전 그리디로 풀면 맞는 해일 것이라는 검증방법이다.  )

 

암튼 이런 사고흐름에 의해, 브루트 포스를 시도해야겠다는 결론에 도달했다. 

 

그리고 부딪힌 문제는 다음과 같다. 

1. 바꿀 자릿수 조합은 어떻게 만들지?

2. 숫자를 자릿수끼리 바꾸는 건 어떻게 하지?

3. 브루트 포스로 할 경우, 정말 완전탐색이면 시간초과가 걸린다. (조합 최대: 자릿수 바꾸는 조합 6C2 = 15, K번 탐색-> K의 15승- > 10^15 정도)

 

해결하기 위한 생각은 다음과 같다. 

1. 조합을 만드는 건 백트레킹에서 자주 사용한 방법이었다.   

   벡트레킹으로 원하는 조합을 만들어 vector에 저장해두었다. 

   다만 3번, 완전탐색에서 가지치기(필요없는 탐색은 즉시 종료해버리기) 를 하기 위해 직전에 어떤 조합으로 바꾸었는지 저장해서, 다음 탐색에서 사용하지 못하도록 하기로 했다. (ex 1,2자리 바꾼 직후에는 1,2 두자리를 바꾸지 않아도 된다.)

   

2. atoi, itoa를 이용해서 문자의 교환 문제로 바꾸어 풀기로 했다. 

3. 1에서 생각한 방법대로 가지치기를 해보자. DFS로 접근할 생각이었다. 

 

 

그러나 시간초과의 문제에 걸리고 말았다.

 

부딪힌 문제를 해결하기 위해 머리를 계속 썼지만, 

이제는 나서서 문제를 푸는 법을 배울 때라는 감이 와서 다시금 서치를 통해 남의 코드를 보고 왔다. 

그리고 찾은 문제들은 다음과 같다.

 

1. 조합을 벡터로 만드는 방법은 괜찮았으나, 어차피 바꿀 2개의 자리수만 고르는 것이기 때문에,

벡트레킹 내에서 이중 for문으로도 도전할 수 있었다.

 

2. 정수로 입력받은 후 itoa, atoi를 썼으나, 그냥 문자열로 입력받아서 가공하는게 낫겠다는 생각이 들었다. 

   정수가 주어질 때는 무조건 정수로 입력받는 것이 굳어져있는 생각인데, 가끔은 다른 방식으로 생각해도 되겠다는 생각이 들었다. 

 

3.  가장 중요한 문제다. 시간초과가 나는 이유를 보았더니,

'132, 3'만 해도 겹치는 경우의 수가 너무 많았다. (직전에 바꾸었던 두 숫자는 안바꾸게끔 했을 때의 그림이다.)

마지막 결과만 보아도 123, 231, 312밖에 없음에도 불구하고 엄청나게 많이 탐색하고 있다. 

 

그런데 여기서 주목해서 보면, 내가 원하는 것은 K번째의 연산 시에 될 수 있는 가장 큰 숫자인 것이고,  K번 일 때 연산시의 큰 숫자라고 생각하면 다이나믹 프로그래밍도 통하지 않는다.

 

그런데 2차원 다이나믹 프로그래밍이라면 이야기는 달라진다. DP의 특성을 만족하려면 가장 끝쪽에서부터 조건이 만족된다. (나에게는 DP가 벡트레킹과 비슷한 성질을 갖고 있는 걸로 느껴지기 때문에 그렇게 표현하겠다. )1. 마지막 K번째 깊이에 도달하면 만들어진 숫자를 반환받는다. 2. K-1번째 깊이에선 만들 수 있는 수들이 다음 K번째에 도달해서 반환받은 숫자들 중 가장 큰 값을 저장한다. 3. ... i번째 깊이에선 해당 수에서 만들 수 있는 수들이 K번째 도달해서 반환받은 숫자들 중 가장 큰 값, 그리고 해당 수가 되면서 K번째에 도달해서 반환받은 숫자들 두 개 중 더 큰 값을 저장한다. 

즉 '132, 3' 입력에서132, depth = 0312 (depth= 1)  231(depth = 1). 123(depth = 1).... 로 DFS를 진행할 때 

DP[312][depth = 1] 의 값은 312일때 이후로 가질 수 있는 가장 큰 수이고, 이 수는 현재 갖고 있는 가장 큰 수 vs 이 수에서 두자리의 수를 바꾼 후 나머지 K번째까지 연산했을 때 도달할 수 있는 큰 수 중에 더 큰 수가 된다. 

 

 

DFS 경로를 적어보면 다음과 같다. 

 

 

 

애초에 가장 큰 값만을 찾고 있기 때문에, max(저장되어있는 가장 큰 값, 나에서 출발한 다른 값들중 가장 큰 값)으로 갱신될 수 있는 것이다. 

 

 

 

2. 구현

이렇게 DFS 와 함께 쓰이는 DP의 구조는 항상 이렇다. 

생각해내는게 가장 좋겠지만,

매번 그렇게 잘 생각나지 않으니 원리를 파악하기 위해 뼈대만을 뽑아보았다. 

 

int DFS(int n, int depth)
{
	if(depth == K)
    	return n;
        
    if(DP[n][depth] != initial)//초기값과 다르다면, 즉 저장되어있다면
     return DP[n][depth]

	for(int i=0;i<M;i++)
    {
    	if(condition[i])//i가 맞는 조건이라면
        {
			select[i] = true; //i를 맞는 조건으로 고른다. 
            m = modify(n, i); //그에 의해서 뭔가를 바꾼다. 
			DP[i][depth] = max(DP[i][depth], DFS(m, depth+1)//여기선 DFS의 인자가 m으로 바뀐다는 점이 좀 특별하다. 
            select[i] = false; //다음 번 조합을 위해서 다시 복원해둔다. 
        }
    }
    return DP[i][depth]
}

 

 

 

실제 구현한 코드는 다음과 같다. 

#include <unistd.h>
#include <stdlib.h>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
vector <pair <int, int> > comb;

int K,N,M,combnum;
string strn;
bool selected[10];
int switched= -1;
int tmax;
int kount= 0;
int finishflag;
#define MAX 1000002
int DP[MAX][20];

int number(int n)
{
    int cnt = 0;
    int copy = n;
    while(copy>0)
    {
        copy /=10;
        cnt++;
    }
    return cnt;
}

string itoa(int n)
{
    char str[100];
    int m = number(n);
    str[m] = '\0';
    while(--m >= 0)
    {
        str[m] = n%10 + '0';
        n /=10;
    }
    return str;
}

int atoi(string str)
{
    int i = -1;
    int ret = 0;
    while(str[++i] != '\0')
    {
        ret = ret * 10 + str[i] - '0';
    }
    return ret;
}

int ft_max(int a, int b)
{
    return a  > b ? a : b;
}

int DFS(int n, int depth)
{
    if(depth == K)
        return n;
    if(DP[n][depth] != 0) {
        return DP[n][depth];
    }

    for(int i=0;i<M;i++)
    {
        for(int j=i+1;j<M;j++)
        {
            if (i==0 && strn[j] == '0') continue;
            swap(strn[i], strn[j]);
            int m = atoi(strn);
            DP[n][depth] = ft_max(DP[n][depth], DFS(m, depth+1));
            swap(strn[i], strn[j]);
        }
    }
    return DP[n][depth];
}

int find()//조합을 골라서 해당 자릿수의 숫자를 교환.
{
    if(M == 1)
        return finishflag=1;
    else
        return DFS(N, 0);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> K;
    strn = itoa(N);
    //K번 동안 자릿수의 교환을 반복해서 최댓값을 찾는다: 브루트 포스.
    //BFS 또는 DFS.
    int ans = find();
    if(finishflag)
        cout << "-1";
    else
    {
        if(ans == 0)
            cout << "-1";
        else
            cout << ans;
    }
//    cout << kount;
}