272번째 문제 - 2494 숫자 맞추기

한국정보올림피아드 지역본선 2009 초등부 5번 문제 숫자 맞추기

포스팅은 뜸하지만 꾸준히 하루에 여섯문제 일곱문제 이상은 풀어가고 있다. 간만에 재밌는 dp 문제를 풀어서 포스팅 한다.

처음 문제를 보고 든 생각은 bfs로 최단거리를 구하려했다. 하지만 자리 수 제한이 10000... 만 자리나 되는 숫자로 bfs 하기는 힘들어 보였고 점화식을 찾아 동적 계획법으로 풀었다.

 - 함수 

 int dp(int state, int add) - state번째 자리에서 시작하는 숫자에 add번 왼쪽으로 돌린 상태에서의 최소 회전 수 반환

- 구해야 하는 값  

 dp(0,0)

- 점화식 

 1. 오른쪽으로 돌릴 때 :  오른쪽 회전은 밑에 다른 숫자에 영향을 주지 않고 자기 자신만 돌아간다.

 따라서 점화식은  dp(state + 1, add) + 왼쪽 회전수

2. 왼쪽으로 돌릴 때 : 왼쪽 회전은 자기 자신을 포함한 아래 모든 숫자가 함께 돌아간다. 

따라서 점화식은 dp(state + 1, (add + 오른쪽 회전수) % 10) + 오른쪽 회전수

그 외에 경로를 저장 해 줘야 해 choice라는 배열을 선언해서 경로를 저장해 주고 재귀적으로 출력한다. 어쩐지 더 효율적인 방법이 있을꺼 같은데 ... 잘 모르겠다. 알면 댓글 좀 ^^ ...

#include <iostream>

#include <string>

#include <algorithm>

#include <memory.h>

using namespace std;

int d[10001][10];

int choice[10001][10];

int n;

string org, dest;

int dp(int state, int add)

{

int &ret = d[state][add];

if (ret != -1) return ret;

int num1 = (org[state] - '0' + add)%10;

int num2 = dest[state] - '0';

if (state == n-1) {

choice[state][add] = num2 - num1;

return ret=  abs(num1 - num2);

}

//감소 

int lv,left;

if (num1 > num2) lv = num1 - num2;

else lv = (10 - (num2 - num1))%10;

left = dp(state + 1, add) + lv;

//증가

int right,rv;

if (num2 > num1) rv = (num2 - num1);

else rv = (10 - (num1 - num2)) % 10;

right = dp(state + 1, (add + rv) % 10) + rv;

if (left < right) choice[state][add] = -lv;

else choice[state][add] = rv;

return ret = min(left, right);

}

void printR(int state, int add) {

if (state == n) return;

if(choice[state][add]!=0)

cout <<state+1<<" "<< choice[state][add]<<endl;

if (choice[state][add] > 0) printR(state + 1, (add + choice[state][add]) % 10);

else printR(state + 1, add);

}

int main()

{

cin >> n;

cin >> org >> dest;

memset(d, -1, sizeof(d));

cout<<dp(0, 0)<<endl;

printR(0, 0);

}