BOJ 1514 자물쇠

원 출처 : 모름

문제 링크 : 

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

문제 설명 : 

 숫자로 이루어진 문자열 2개가 주어지는데 첫 번째 문자열을 두번 째 문자열로 바꾸는데 드는 최소 코스트를 구하는 문제.

 문자열에 가할 수 있는 연산은 최소 1개에서 최대 3개를 선택해서 그 값을 한꺼번에 최대 1이상 3이하 증가/감소 시킬 수 있다. 물론 숫자는 0~9까지만 사용하며 0밑으로 내려가면 9로, 9 이상으로 올라가면 0으로 다시 돌아간다. 즉 숫자를 회전시키는 것이라고 볼 수 있다.

dp 상태 정의 :

dy[n][t1][t2] :: 첫번째 부터 n번째까지 자물쇠를 돌렸을 때 n번째 숫자가 t2고 n-1번째 숫자가 t1이고 1~n-2까지의 숫자는 목표 다이얼을  완성한 상태 

t1과 t2는 0~9까지 값을 가진다.

전처리가 좀 필요한데 다른 분들은 수식만으로 구하신 것 같지만 나는 멍청함으로 수식따위 구하지 않고 직접 bfs를 사용해서 구했다.

 가장 기초적인 전처리 방법은  

 pre[s1][s2][s3][t1][t2][t3] :: 세 다이얼이 s1, s2, s3일 때 t1, t2, t3로 변환하기 위한 최소 코스트

 근데 이걸 전처리하기 너무 귀찮다. 일단 더럽게 배열이 6차원이다. 

이 전처리를 줄일 수 있는데 s1, s2, s3, t1, t2, t3 정보가 모두 필요하지 않다는 데 핵심 아이디어가 있다. 실제로 필요한 정보는 (t1 -s1), (t2 - s2), (t3- s3) 정보다. 따라서 전처리 해야하는 내용을  

 pre[s1][s2][s3]  원래 다이얼로 부터 차이 값이 s1, s2, s3일 때 변환하기 위한 최소 코스트 

로 정의 할 수 있다. 물론 구현의 편의상 (-1 == 9) (-2 == 8) ... 이다. 따라서 s1, s2, s3 는 모두 0에서부터 9사이의 값을 가진다. 

dp 점화식 :

여기서 

n2 == 원래 다이얼의 n번째 숫자 

t0 == 목표 다이얼의 n-2번째 숫자

cost((s0,s1,s2) ->(t0,t1,t2)) 는 pre[t0-s0][t1-s1][t2-s2]이다.

디피 테이블 하나를 체우는데 10^2이 들고 모든 테이블을 체우기 위해서는 n*10^2이 드므로 시간복잡도는 n* 10^4 

상당히 많이 틀렸던 문제. 

이문제를 처음 틀리고 나는 완벽한데 틀렸다며 부들부들했던 문제다.

실수할 여지가 좀 많다.

완전 알고리즘을 못하던 시절에 손댔다가 실패했던 문젠데 생각이 나서 풀고 해설을 써본다.(실제로 BOJ 자물쇠에 대한 풀이를 원하시는 분들이 많다고 들었다)

소스코드는... 더럽다. 알아서 읽어보세여 ^ㅇ^ (심지어 변수명도 다름)

소스보기