[S1] 12852. 1로 만들기 2

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

12852번: 1로 만들기 2

2가지 방법을 가져왔다. 첫 번째 방법과 두 번째 방법은 해결한 방식의 차이가 크다. 천천히 살펴보자.

 

1. 1부터 시작하여 N까지의 최소값을 구하기.

1부터 시작해서 N까지 가는데, 이렇게 하는 것이다.

1로 갈 수 있는 숫자 -> 3, 2 -> 2와 3의 최소 횟수 갱신과 동시에 1을 저장.

2로 갈 수 있는 숫자 -> 2, 4, 6 -> 2, 4, 6의 최소 횟수 갱신이 가능할 경우 갱신 (최소 경로 값과 2)

3으로 갈 수 있는 숫자 -> 4, 6, 9 -> 최소 횟수 갱신이 가능할 경우 갱신

 

1을 접근했을 경우

1	2	3	4	5	6	7	8	9	10
0	1	1	1e9	1e9	1e9	1e9	1e9	1e9	1e9
0	1	1

 

2로 접근했을 경우

1	2	3	4	5	6	7	8	9	10
0	1	1	dp[2][0] + 1 = 2	1e9	dp[2][0] + 1 = 2	1e9	1e9	1e9	1e9
0	1	1	2로 접근		2로 접근

 

3을 접근했을 경우

1	2	3	4	5	6	7	8	9	10
0	1	1	2	1e9	2	1e9	1e9	dp[3][0] + 1 = 2	1e9
0	1	1	2		2			3으로 접근

이런식으로 1 ~ N까지 접근하면 dp[N][0]의 값이 최소 경로가 될 것이고, dp[N][1]을 따라 가다보면 그 경로를 알 수 있게 된다.

 

코드는 다음과 같다.

#include <cstdio>

int dp[1000001][2];
int main(void) {
    int N; scanf("%d", &N);
    int idx = N;
    dp[1][0] = 0;
    for (int i = 2; i <= N; i++) dp[i][0] = 1e9;
    for (int i = 1; i < N; i++) {
        if (i * 3 <= N && dp[i * 3][0] > dp[i][0] + 1) dp[i * 3][1] = i, dp[i * 3][0] = dp[i][0] + 1;
        if (i * 2 <= N && dp[i * 2][0] > dp[i][0] + 1) dp[i * 2][1] = i, dp[i * 2][0] = dp[i][0] + 1;
        if (dp[i + 1][0] > dp[i][0] + 1) dp[i + 1][1] = i, dp[i + 1][0] = dp[i][0] + 1;
    }
    printf("%d\n", dp[N][0]);
    while (idx != 1) {
        printf("%d ", idx);
        idx = dp[idx][1];
    }
    printf("1");
}

하지만 이 방식은 dp[1000001][2]만큼의 공간이 필요하다. 그래서, 이러한 공간이 필요 없는 방법이 존재하는데, 그 방법이 2번 방법이다.

 

 

2. dfs와 map을 사용한 dp

dfs를 활용하여 1을 만드는 최소 갯수는 다음 글을 통해 알 수 있다.

https://jhcard.tistory.com/139

[S3] 1463. 1로 만들기

이 글에 나오는 dfs함수를 참고하고, n1 < n2일 경우 map[num] = num / 3을 저장하고, 이외에는 map[num] = num / 2를 저장해준다. 그러면 dfs(N)으로 최소 값을 알 수 있게 되고, map을 되돌아가다보면 그 경로를 출력할 수 있게 되는 것이다.

코드는 다음과 같다.

#include <cstdio>
#include <map>

std::map<int, int> m;
int dfs(int n) {
    if (n <= 1) return 0;
    int a = dfs(n / 3) + n % 3;
    int b = dfs(n / 2) + n % 2;

    if (a < b) {
        m[n] = n / 3;
        return a + 1;
    }
    else {
        m[n] = n / 2;
        return b + 1;
    }
}

int main(void) {
    int N; scanf("%d", &N);
    printf("%d\n", dfs(N));
    while (N > 1) {
        int next = m[N];
        printf("%d ", N);
        while (N != 2 * next && N != 3 * next) printf("%d ", --N); 
        N = next;
    }
    printf("1");
}