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를 갱신하면 됩니다.
자세하게 쓰지는 않았지만 고민을 조금 해보시면 이해할 수 있을 것입니다. 참고로 제 코드는 심각하게 꼬여있습니다 ㅎㅎ..
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 1027번: 고층 건물 (0) | 2018.02.12 |
---|---|
[BOJ] 1025번: 제곱수 찾기 (6) | 2018.02.11 |
[BOJ] 1023번: 괄호 문자열 (2) | 2018.02.11 |
[BOJ] 1019번: 책 페이지 (4) | 2018.02.07 |
[BOJ] 1014번: 컨닝 (0) | 2018.02.07 |
[BOJ] 1300번: K번째 수 (0) | 2018.02.05 |