⚽ 수열 추측하기
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼
의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3
1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하
시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
▣ 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의
미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
▣ 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재
하지 않는 경우는 입력으로 주어지지 않는다.
▣ 입력예제 1
4 16
▣ 출력예제 1
3 1 2 4
import sys
sys.stdin = open("input.text", "rt")
N, F = map(int, input().split())
res = [0] * N
ch = [0] * (N+1)
b = [1] * N
#이항계수 먼저 구해놓기
for i in range(1, N):
b[i] = b[i-1] * (N-i) // i #이항정리 코드 암기.
def DFS(L, sum): #sum은 마지막 숫자로 향해가는 수
if L == N and sum == F:
for x in res:
print(x, end = " ")
sys.exit(0)
else:
for i in range(1, N+1):
if ch[i] == 0:
ch[i] = 1
res[L] = i
DFS(L+1, sum + (res[L] * b[L]))
ch[i] = 0
DFS(0,0)
⚽ 코멘트
이 문제는 접근하는 방법을 생각할 필요가 있었다.
N = 4인 경우 1~4까지 나열되어 있을 때 파스칼 삼각형처럼 더해나가면서 결과를 도출하는 것이었다.
이 문제는 결과 리스트를 미리 만들고 F라는 값이 나올 때까지 다 해볼까? 라는 생각을 가졌으면 잘 접근했다. 왜냐하면 거꾸로 올라가는 방식은 생각할 수 없기 때문...
근데 !! 이 문제는 수학적 규칙성을 알았다면 매우 쉽게 풀 수 있었다.
문제 자체를 +로 나열해보면 더 쉽게 이해할 수 있는데,
가장 끝 쪽에 있는 것은 1번씩만 나오고 중간 것들은 3번씩 등장. 규칙(이항정리)은 어릴 때 배웠으니 넘어가겠다.
-
이항계수를 알았다면 문제를 쉽게 풀 수 있었다. (미리 저장해놓고 해당 값을 쓴다면 쉽게 풀 수 있음)
-
(이항 계수는 Nc0 Nc1 Nc2 ... NcN 까지 가는거였잖아)
for i in range(1, N+1):
if ch[i] == 0:
ch[i] = 1
res[L] = i
DFS(L+1, sum + (res[L] * b[L]))
ch[i] = 0위와 같이 원래 넣으려는 값과 최종 나오는 횟수를 곱해서 다음으로 넘기는거야! 그 외는 '순열'이랑 똑같아.
이런 문제는 처음부터 생각을 어떻게 해야할지 아직 나도 감이 잘 안온다. 문제를 많이 풀어보는 수 밖에 !
다시 풀어본 코드
import sys
n,m = map(int, input().split())
data = list(range(1,n+1))
com = [1] # 콤비네이션 값 저장을 위해 무조건 시작값1
top = 1
bottom = 1
for i in range(1,n):
top *= (n-i)
bottom *= i
com.append(top // bottom)
# 콤비네이션 값 완성.
print(*com)
def calResult(lis): #리스트 들어오면 최종값 계산
res = 0
for i in range(n):
res += com[i] * lis[i]
return res
choice = []
ch = [0] * (n+1) # 중복 체크
def dfs(L):
if L == n: # 모두 선택. 종료조건
if calResult(choice) == m:
print(*choice)
exit(0)
else:
for i in range(1,n+1):
if ch[i] == 0:
ch[i] = 1 # 방문 처리
choice.append(i)
dfs(L+1)
ch[i] = 0
choice.pop()
dfs(0)- 콤비네이션 값 저장해둔 후에 다 선택한 경우 그때 계산하는 걸로.
