[BOJ] 1463번: 1로 만들기

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

 

 

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

풀이

다른 실버4 DP 문제와 비슷한 난이도로 느껴졌다.

N에 대하여, N//3, N//2, N-1까지의 수를 만드는 최솟값에 + 1을 하는 식으로 풀면 된다.

이문제 역시 재귀함수를 사용하여 풀기 위해 노력했지만... 시간초과 😮‍💨

 

#시간초과 걸린 코드
import sys     
sys.setrecursionlimit(10000000)

def DP(n):
    if n == 2 or n == 3: return 1
    if dp[n]: return dp[n]

    dp[n] = DP(n - 1)
    if n % 3 == 0: dp[n] = min(dp[n], DP(n//3))
    if n % 2 == 0: dp[n] = min(dp[n], DP(n//2))
    dp[n] += 1

    return dp[n]

N = int(input())
dp = [0] * (N + 1)
print(DP(N))

 

위에 코드 시간초과 걸린 거 보고 갑자기 화나서 c++로 시도했다

 

#include <iostream>

using namespace std;

int DP(int n, int* p) 
{
    if (n == 2 || n == 3) return 1;
    if (p[n]) return p[n];

    p[n] = DP(n - 1, p);

    if (n % 3 == 0) p[n] = p[n] < DP(n/3, p) ? p[n] : DP(n/3, p);
    if (n % 2 == 0) p[n] = p[n] < DP(n/2, p) ? p[n] : DP(n/2, p);

    return ++p[n];
}

int main()
{
    int N;
    cin >> N;

    int dp[N + 1] = {0}; //이부분 문제
    cout << DP(N, dp) << endl;

    return 0;
}

 

오랜만에 해서 가물가물...해서 그런지 dp 배열이 초기화가 안된다고 뜨던데... 그래서 걍 다시 파이썬으로 틀었다 ㅋ 와리가리레전드줏대없녀

근데 그와중에 코딩도 잘못한듯? dp 배열 초기화 안하고 10 넣었더니 -3이 출력됨...

 

⤵️ 제출한 코드

N = int(input())
dp = [0] * (N + 1)

for i in range(2, N + 1):
    if i == 2 or i == 3:
        dp[i] = 1
    else:
        dp[i] = dp[i - 1]

        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2])
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3])
        dp[i] += 1

print(dp[N])

 

1. N을 입력받는다.

2. dp 배열을 0으로 초기화한다.

3. dp[1]은 0이므로 따로 처리하지 않고, dp[1]에서 1을 더하고, 2를 곱하고, 3을 곱한 값인 dp[2], dp[3]을 1로 설정한다.

4. dp[i //2], d][i // 3] 값은 각각 2, 3으로 나누어질 때만 가능한 값이기 때문에, 무조건 있는 dp[i - 1]을 dp[i] 값으로 설정한다.

5. 그후 2, 3 각각 나눠진다면 나눈 값에 대한 더 적은 값으로 설정한다.

6. 나누기 2, 나누기 3, -1 까지의 횟수에 1을 더해야 하므로 1을 더한다.

 

그냥 앞으로는 top-down 방식 쓸 생각 말고 반복문 써야겠다는 교훈을 얻음.