백준 1052번 물병

문제 링크입니다: https://www.acmicpc.net/problem/1052

1052번: 물병

이 문제의 경우 직접 여러 케이스들을 계산해보며 규칙을 구해야 하는 문제였습니다.

우선, 물통을 하나도 사지 않고 최대로 물병을 합쳤을 때 남은 물병의 수는 아래와 같습니다.

1. N=2: [1, 1] -> [2] 한병

2. N=3: [1, 1, 1] -> [2, 1] 두병

3. N=4: [1, 1, 1, 1] -> [2, 2] -> [4] 한병

4. N=5: [1, 1, 1, 1, 1] -> [2, 2, 1] -> [4, 1] 두병

5. N=6: [1, 1, 1, 1, 1, 1] -> [2, 2, 2] -> [4, 2] 두병

6. N=7: [1, 1, 1, 1, 1, 1, 1] -> [2, 2, 2, 1] -> [4, 2, 1] 세병

7. N=8: [1, 1, 1, 1, 1, 1, 1, 1] -> [2, 2, 2, 2] -> [4, 4] -> [8] 한병

8. N=9: [1, 1, 1, 1, 1, 1, 1, 1, 1] -> [2, 2, 2, 2, 1] -> [4, 4, 1] -> [8, 1] 두병

...

 

이렇게 직접 시뮬레이션을 돌린 결과 저는 물병을 하나도 사지 않았고 N이 2의 n제곱승일 경우 물병 한병으로 합칠 수 있다는 규칙을 찾을 수 있었습니다.

또한, 문제에 새로운 물병을 살 수 있다는 조건이 있고 물병을 계속 구매할 경우 결국 물병의 개수가 2의 n 제곱승이 될 것이고 K는 자연수이므로 최소 1이기 때문에 불가능한 경우는 없다는 것 또한 알 수 있었습니다.

여기까지 왔다면 문제는 다 푼 거나 다름이 없습니다. 알고리즘은 아래와 같습니다.

 

전제조건: N은 주어진 물병의 개수, cnt: 들고 가는 물병, result: 상점에서 구매한 물병의 개수

1. 주어진 물병을 최대한 합칩니다. 즉, N을 2로 나눕니다.

2. 1번에서 나머지가 발생한다면 합쳐지지 않은 물병이 존재한다는 것이므로 cnt를 1 추가해줍니다.

3. N이 0이 될 때까지 1번과 2번을 반복해줍니다.

4. cnt의 개수가 K 이하일 경우 조건이 성립하므로 result를 출력해주고 프로그램을 종료합니다.

5. 4번에서 조건이 성립하지 않을 경우 1 ~ 4번을 반복해줍니다.

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~