BOJ 2309 - 일곱 난쟁이
https://www.acmicpc.net/problem/2309 KOI 2004 초등부 지역본선 문제라고 한다.
시간재면서 문제 푸는 연습을 해보고 싶어서 하나 잡아서 해본건데, 19분 정도 걸렸다.
풀이법을 생각해내는데는 다행히 얼마 안걸렸지만 터무니없는 실수를 하는 바람에 예상 시간보다 5분정도 더 걸렸다..
내 풀이법이 최적해는 아닐 수 있지만 일단 개인적으로 정리하는 느낌으로 적어보려고 한다.
풀이법
9개의 숫자를 입력 받고, 이 중에서 합계가 100이 되는 숫자 7개를 찾아내야 한다.
처음에는 ‘각 케이스별로 일일히 합계를 구해야되는건가?’ 하는 생각을 했는데, 조금 다르게 생각해보니 대입해야하는 경우의 수가 많이 줄어들었다.
9개의 숫자를 모두 합한뒤에, 여기서 100을 빼면 골라내야 하는 숫자 두개의 합계가 나온다.
편의상 골라내야 하는 숫자 두개의 합계는 select로 설명하겠다.
int select = total - 100
골라낼 숫자의 합을 찾아낸 뒤, 배열을 오름차순으로 정렬해주고 이중 for문을 돌려서 찾아내면 된다.
나같은 경우는 num[a] + num[b] == select 를 만족하는 경우 num[a]와 num[b]를 0으로 바꿔주고, num배열에 들어있는 값이 0이 아닌 애들만 차례대로 출력되게 구현했다.
주의할 점이 있다면 ‘가능한 정답이 여러가지인 경우’가 있다는 것이다. 정답을 찾은 시점에서 for문을 벗어나도록 신경써주자. (정답을 찾고 나서도 for문을 계속 돌아가게 구현하는 바람에 일부 case에서 fail이 났었다..)
소스 코드 (Java)
링크 참고.