[백준] No.2494 - 숫자 맞추기 (C++, DP)

문제

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

2494번: 숫자 맞추기

 

 

풀이

 

solved.ac 난이도: Platium 5

 

역추적의 구현과 숫자 나사의 현재 상태를 구하는 것이 중요했던 DP 문제.

 

일단, 숫자나사는 최대 10,000개 존재할 수 있기 때문에 왼쪽으로 돌릴때 마다 하위의 나사들을 모두 변형해주는 것은 너무 비효율적이다.

사실 각 나사가 왼쪽으로 회전한 횟수만 알 수 있으면 현재의 상태를 구할 수 있다.

특히, 왼쪽으로 돌리는 것에 영향을 받지 않기위해 위에서 부터 순서대로 나사를 맞춰나가야 하기때문에 상위 나사 중에서 왼쪽으로 회전한 횟수를 저장하면 이를 구할 수 있다.

왼쪽으로 돌리는 경우 10번 돌게 되면 다시 원위치로 돌아오기 때문에 회전횟수가 10이상 인경우 MOD연산을 통해 0~사이의 값만 가지도록 구현해주자.

 

각 나사는 왼쪽 또는 오른쪽으로 돌수 있으므로 어느 쪽으로 회전하는 것이 전체 회전수를 줄여주는 구해야한다.

dp[회전나사 번호(idx)][현재 나사 정면의 수(num)]는 해당 번호의 회전 나사(idx)가 num일때 하위의 모든 나사가 최종 상태에 도달하는 최소 회전수를 저장한다.

 

 

특히 이번 문제는 답으로 도달하는 과정을 역추적해야 하므로 다음과 같은 구조체를 메모이제이션에 사용했다.

 

typedef struct state {
    int total_turn = -1;    //전체 회전횟수
    int turn = 0;            //이번 나사에서의 회전
}State;

 

total_turn에는 하위의 모든 나사가 최종 상태에 도달하는 전체의 최소 회전수를

turn에는 최적해를 위해 이번 나사가 왼쪽 또는 오른쪽으로 몇번 회전해야 하는지를 저장한다.

 

상위 나사에서의 왼쪽 회전 수를 통해 이번 나사(idx)의 상태(num)를 구하고

왼쪽과 오른쪽으로 회전하는 두가지 경우로 분기하여 답을 구하면된다.

 

int TurnScrew(int left_turned, int idx) {
    if (idx == screw_num)
        return 0;
 
    int num = init[idx] + left_turned;
    num %= MOD;
 
    int& ret = dp[idx][num].total_turn;
    if (ret != -1)
        return ret;
 
    int right; //오른쪽으로 돌려야하는 횟수
    if (dest[idx] > num)
        right = num + 10 - dest[idx];
    else
        right = num - dest[idx];
 
    int left; //왼쪽으로 돌려야하는 횟수
    if (dest[idx] >= num)
        left = dest[idx] - num;
    else
        left = dest[idx] + 10 - num;
 
    int left_num = TurnScrew((left_turned + left) % MOD, idx + 1) + left;
    int right_num = TurnScrew(left_turned, idx + 1) + right;
    
    if (left_num < right_num) {    //더 조금 돌려도 되는 것이 최적해가 된다.
        ret = left_num;
        dp[idx][num].turn = left;
    }
    else {
        ret = right_num;
        dp[idx][num].turn = -right;
    }
 
    return ret;
}

 

 

 

코드