백준 1463 1로 만들기 / C++

문제 : 링크텍스트

풀이 point

bfs를 활용한 풀이도 가능하고
dp를 활용한 풀이도 가능하다.

이번에는 dp를 활용하여 문제를 풀었다.
만약 12를 1로 만들기 위한 최소 횟수를 구해본다고 하자.
1~11까지를 1로 만들기 위한 최소 횟수를 알고 있다면
12는 총 3가지 방법으로 구할 수 있다.

12/3 -> 4를 만들기 위한 최소 횟수에 +1
12/2 -> 6을 만들기 위한 최소 횟수에 +1
12-1 -> 11을 만들기 위한 최소 횟수에 +1

이런 방식으로 답을 구할 수 있게 되는데 이를 점화식으로 고쳐보게 되면
dp[i] = min(dp[i/2], dp[i/3], dp[i-1])+1이 되게 된다.

물론 i가 2 or 3으로 나누어지는 경우에만 i/2, i/3이 필요한 것이고
11같이 2 또는 3으로 나누어지지 않는 수는 dp[10] + 1을 진행하면 된다.

풀이 순서

dp를 위한 점화식을 도출해낸다.
총 3가지의 방법 중 가장 최소를 선택하는데 미리 구해놓은 값을 통해 연쇄적으로 도출해낸다고 생각하자.

그외 살펴볼 점

문제에 대한 얘기는 아니지만 문제를 풀면서 오류가 생겼던 점을 짚고 넘어가려한다.
dp배열을 전역변수가 아닌 지역변수로 선언했더니 프로그램이 강제종료 됐다.
대체 무엇이 문제인가 했는데 지역변수로 선언하면 스택메모리를 차지하게 된다.
그 메모리가 너무 커서 초기화하는데 오랜시간이 걸려 프로그램이 강제 종료 된것이었다. 전역변수로 선언하면 스택메모리가 아닌 데이터 영역에 저장되므로 괜찮다고 한다.

너무 큰수는 전역변수로 선언해야한다는 정보를 얻었다.

코드

//백준 1463, 1로 만들기

#include <iostream>
int dp[1000000]; //지역변수로 선언하면 시간 오래 걸림(아예 멈춤춤)
int main(){
    int N;
    
    std::cin >> N;
    
    dp[2] = 1;
    for(int i{3}; i<=N; ++i){
        dp[i] = dp[i-1] + 1;
        if(i%2==0) dp[i] = std::min(dp[i], dp[i/2]+1);
        if(i%3==0) dp[i] = std::min(dp[i], dp[i/3]+1);
    }

    std::cout << dp[N];
    return 0;
}

2025-01-08T12:50:37.347Z