가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다.
그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.
단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
▣ 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.
N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
▣ 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.
답이 존재 하지 않는 경우는 입력으로 주어지지 않는다.
▣ 입력예제
4 16
▣ 출력예제
3 1 2 4
내가 쓴 코드1
#내가 쓴 코드1
import sys
sys.stdin = open("input.txt",'rt')
def DFS(v):
global result
if v == N:
ch = result.copy()
while len(ch) > 1:
for i in range(len(ch)-1):
ch[i] = ch[i]+ch[i+1]
ch.pop()
if ch[0] == F:
for x in result:
print(x, end = ' ')
sys.exit(0)
else:
for j in range(1,N+1):
if check[j] == 0:
result[v] = j
check[j] = 1
DFS(v+1)
check[j] = 0
if __name__ == "__main__":
N, F = map(int, input().split())
result = [0]*N
check = [0]*(N+1)
DFS(0)
내가 쓴 코드2
#내가 쓴 코드2
import sys
#sys.stdin = open("input.txt",'rt')
input = sys.stdin.readline
def DFS(v):
if v == N:
tmp = 0
for c in range(N):
tmp += result[c]*weight[c]
if tmp == F:
for x in result:
print(x, end=' ')
sys.exit(0)
else:
for k in range(1,N+1):
if dup_check[k] == 0:
result[v] = k
dup_check[k] = 1
DFS(v+1)
dup_check[k] = 0
if __name__=="__main__":
N,F = map(int, input().split())
result = [0]*N
dup_check = [0]*(N+1)
weight = [0]*N
for i in range(N):
if i == 0:
weight[i] = 1
else:
tmp = 1
for j in range(i):
tmp *= (N-1-j)
tmp /= (j+1)
weight[i] = int(tmp)
DFS(0)
모범답안
#모범답안
import sys
#sys.stdin = open("input.txt",'rt')
def DFS(L,sum):
if L==n and sum==f:
for x in p:
print(x, end=' ')
sys.exit(0)
else:
for i in range(1,n+1):
if ch[i] == 0:
ch[i] = 1
p[L] = i
DFS(L+1, sum+(p[L]*b[L]))
ch[i] = 0
if __name__ == "__main__":
n, f = map(int, input().split())
p = [0]*n
b = [1]*n
ch = [0]*(n+1)
for i in range(1,n):
b[i] = b[i-1]*(n-i)//i
DFS(0,0)
느낀점
1. 일단 중복 되는지 안되는지 안써있어서 중복 되는걸로 풀었는데
중복 안되는거라서 좀 짜중났다. 근데 그건 예제만 봐도 알 수 있었는데
내가 바보지!!!갠차낭.
2. 중복은 check리스트로 컨트롤하고, 여러개의 가지는 반복문을 이용하고,
DFS(다음레벨) 전은 컨디션 조정, 그리고 후는 컨디션 원래대로 복구
이렇게 흘러가는 흐름을 이제 많이 익힌 것 같다.
DFS 정의 시 if-else문을 기본으로 하되, if에서는 종료 조건을,
else에서는 계속되는 탐색 및 재귀호출!
잘하구이땅~ 100점은 나왔지만.. 좀 오래걸렸으니 모범답안 보고 다시 풀어봐야지
3. 모범답안은 파스칼의 삼각형에서 숫자가 더해지는 규칙을 이용해서 풀었당...
수학 역량 부족이 여기서 드러나는걸까..흑
배운 기억은 있는데 규칙 이용할 생각은 안했다.
규칙이용해서 먼저 다시 풀어봐야지
4. 조합을 구현하는(weight 값 넣기) 코드를 내가 좀 비효율적으로 했넴..쩝
모범답안의 조합 구현이 combination 정의에 맞는 풀이인것같다! 보고배우장.
다시 풀어보기
#다시 풀어보기
import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline
def DFS(v, current_sum):
if v == N and current_sum == F:
for x in result:
print(x,end=' ')
sys.exit(0)
else:
for j in range(1,N+1):
if dup_check[j] == 0:
result[v] = j
dup_check[j] = 1
DFS(v+1, current_sum + (result[v]*weight[v]))
dup_check[j] = 0
if __name__=='__main__':
N,F = map(int, input().split())
result = [0]*N
weight = [1]*N
dup_check = [0]*(N+1)
for i in range(1, N):
weight[i] = weight[i-1]*(N-i)//i
DFS(0,0)