[BOJ] 1020번: 디지털 카운터

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

 

쉬운 문제인줄 알았는데 생각보다 재밌는? 어려웠던? 문제였습니다.

 

일단 딱 생각해도 그냥 직접 계산하는 방식으로 풀려고 하면 111111111111 혹은 88888888888과 같은 입력이 들어왔을 때 반드시 10^N번 연산을 해야하니까 값이 클 경우 불가능함을 알 수 있습니다. 맨 처음에는 생각을 얕게 해서 11..1 // 88....8만 따로 예외처리하고 나머지는 직접 계산하면 되겠다고 안일하게 생각했는데 7888....8 과 같은 입력까지 고려하면 그게 불가능함을 알 수 있었습니다.

 

그렇게 고민을 계속하다가 떠올린 풀이는 DP입니다.

 

D[i][j] : i자리의 합이 j가 되는 가장 작은 수. ex) D[2][6] = 14.(14를 만드는데 선분 6개 필요, 선분 6개가 필요한 2자리 수 중에서 14가 최소)

 

이라고 정의를 하겠습니다.

 

이 때 D[i][j]는 D[i-1][0~j]로 계산이 가능합니다. 이렇게 DP 테이블을 우선 다 채워둔 후에, 아래와 같은 방식으로 문제를 해결합니다.

 

ex) 입력 7788

 

i) ans를 10^4으로 초기화합니다.

 

ii) 맨 처음에 778X를 생각합니다. 끝 자리를 0~9로 대입하면서 7788과 동일한 선분을 가지는 수가 존재하는지 확인하고, 그 수에 대해서 ans를 갱신해줍니다. 지금의 경우에는 끝자리가 8일 때 유일하게 가능하므로 ans는 여전히 10000입니다.

 

iii) 77XX를 생각합니다. 끝에서 두 번째 자리를 0~9로 대입하면서 7788과 동일한 선분을 가지는 수가 존재하는지 확인합니다. 이는 D[1][14-cnt[0]], D[1][14-cnt[1]], D[1][14-cnt[2]], ... , D[1][14-cnt[9]] 를 확인하면 됩니다. 이후 ans를 갱신합니다. 참고로 ans는 여전히 10000입니다.

 

iv) 7XXX를 생각합니다. 끝에서 세 번째 자리를 0~9로 대입하면서 7788과 동일한 선분을 가지는 수가 존재하는지 확인합니다. 이는 D[2][17-cnt[0]], D[2][17-cnt[1]], .. , D[2][17-cnt[9]]를 확인하면 됩니다. 이후 ans를 갱신합니다. 이 때 ans는 7804로 갱신됩니다.

 

v) 이런식으로 모든 자리에 대해 확인하고 ans를 갱신하면 됩니다.

 

자세하게 쓰지는 않았지만 고민을 조금 해보시면 이해할 수 있을 것입니다. 참고로 제 코드는 심각하게 꼬여있습니다 ㅎㅎ..

 

https://github.com/blisstoner/BOJ/blob/master/1020.cpp