역방향 자릿수 합
면접 대비시간 제한1초메모리 제한1024 MB
N과 목표 합이 주어졌을 때 1부터 N까지의 수를 한 번씩 배열해 인접한 수를 반복해 더한 결과가 목표 합이 되는 순열 중 사전순으로 가장 앞선 것을 구합니다.
문제
FJ와 그의 소들은 암산 게임을 즐긴다. 1부터 N까지의 수(1 ≤ N ≤ 10)를 정해진 순서로 적고, 인접한 두 수를 더해 수가 하나 적은 새 목록을 만든다. 목록에 수가 하나만 남을 때까지 이 과정을 반복한다. 예를 들어 N=4인 경우 게임은 다음과 같이 진행된다.
3 1 2 4
4 3 6
7 9
16
소들은 이제 더 어려운 게임을 시작했다. 최종 합과 N만 보고 처음 수열을 알아내는 게임이다. 이 암산은 FJ에게 조금 버거우므로, FJ가 소들과 같이 게임을 따라갈 수 있도록 도와주는 프로그램을 작성하라.
입력
첫 줄에 공백으로 구분된 두 정수 N과 최종 합이 주어진다.
출력
주어진 합을 만드는 1부터 N까지 정수의 순서를 출력한다. 해가 여럿이면 사전순으로 가장 앞선 것, 즉 작은 수가 앞에 오는 순서를 출력한다.