테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== Construct a Coin Set ======

===== 풀이 =====
  * 동전 집합이 주어졌을때, 그리디 솔루션과 옵티멀 솔루션이 다른 값을 갖게 되는 최소 금액을 찾는 문제는 나름 유명한 문제이다. ([[ps:tutorial:동전 문제#Canonical Coin System 여부 체크하기]] 참고)
  * 여기에서는 역으로 그리디 솔루션과 옵티멀 솔루션이 다른 값을 갖게 되는 최소 금액이 주어졌을때, 거기에 해당하는 동전 집합을 만들라는 문제이다.
  * 가장 단순하게 구성해보면, N을 최적 방법으로는 2개의 동전으로 만들수 있지만, 그리디하게 만들면 3개의 동전이 필요하도록 할수 있다. 가장 싼 동전은 1로 고정되어있으므로 가장 비싼 동전이 N-2라면, 그리디 솔루션으로는 3개가 필요하다. 이제 남은 동전중에서 2개를 가지고 N을 만들수 있도록 추가해주기만 하면 된다. 나는 N이 짝수일때 N/2 동전을, 홀수일때 ceil(N/2)와 floor(N/2) 동전을 추가하도록 했다. 다른 사람들의 답을 보니 3와 N-3을 추가하는 좀 더 간단한 방식도 있었다. 어떻게 하든 N-1 까지는 그리디하게 구해도 옵티멀이 된다는 것은 쉽게 알 수 있다.
  * 그리고 어떻게 하든 최소 반례가 5 이하가 되는 동전 집합은 존재하지 않는다는 것도 쉽게 알수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 32462. Construct a Coin Set".

- Problem link: https://www.acmicpc.net/problem/32462
- Solution link: http://www.teferi.net/ps/problems/boj/32462

Tags: [ad hoc]
"""

import sys
from teflib import psutils


@psutils.run_n_times
def main():
    N = int(sys.stdin.readline())

    if N <= 5:
        print('-1')
    elif N % 2 == 0:
        print('3')
        print(1, N // 2, N - 2)
    else:
        print('4')
        print(1, N // 2, (N + 1) // 2, N - 2)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}