본문 바로가기

개발공부27

[SWEA 5255][Python] [파이썬 S/W 문제해결 최적화] 2일차 - 타일 붙이기 코드 ## SWEA 5255 T = int(input()) for test_case in range(1 ,T+1): N = int(input()) arry = [-1]*(N+1) for i in range(1,N+1): if i == 1 : arry[i] = 1 elif i == 2 : arry[i] = 3 elif i == 3 : arry[i] = 6 else : arry[i] = arry[i-1] + 2*arry[i-2] + arry[i-3] print(f"#{test_case} {arry[N]}") 풀이 상향식 방법으로 점화식을 찾는게 어려웠다. arry[N]을 만드는 방법은 반복을 제외하고 3가지가 있는데, 1) arry[N-1]일 경우 : 2x1 타일 하나를 새로로 붙인다. 2) arry[N-2.. 2022. 12. 28.
[SWEA 5256][Python] [파이썬 S/W 문제해결 최적화] 2일차 - 이항계수 코드 ## SWEA 5256 T = int(input()) for test_case in range(1,T+1): n,a,b = map(int, input().split()) dp = [[0]*(n+1) for _ in range(n+1)] t = min(a,b) for i in range(0, n+1): for j in range( min(i, t)+1 ) : if dp[i][j] == 0 : if j == 0 or j == i : dp[i][j] = 1 else : dp[i][j] = dp[i-1][j] + dp[i-1][j-1] print(f"#{test_case} {dp[n][t]}") 풀이 2차원 list dp에 2중 for 문을 돌면서 계수를 update한다. 여기서 DP를 사용하기 위해서 이.. 2022. 12. 28.
[SWEA 5258][Python] [파이썬 S/W 문제해결 최적화] 3일차 - 해피박스 코드1 - DFS ## SWEA 5258 dfs 풀이 T = int(input()) def dfs(w,k,local_value): global result if w >= 0 : if k > N : if result < local_value : result = local_value else : dfs(w-w_arry[k],k+1,local_value+v_arry[k]) dfs(w, k + 1, local_value) for test_case in range(1,T+1): W,N = map(int, input().split()) w_arry = [0 for _ in range(N+1)] v_arry = [0 for _ in range(N+1)] for i in range(1,N+1): w_arry[i], v.. 2022. 12. 28.
[SWEA 5260][Python][파이썬 S/W 문제해결 최적화] 3일차 - 부분 집합의 합 코드 ## SWEA 5260 T = int(input()) for test_case in range(1,T+1): N,K = map(int, input().split()) result = 0 arry = [ [N,0] ] while arry : cur = arry.pop() if cur[0] == 0 : continue bound = cur[0]*(cur[0]+1)/2 + cur[1] if bound >= K : if cur[0]+cur[1] == K : result += 1 elif cur[0] + cur[1] < K : arry.append([ cur[0]-1,cur[0]+cur[1] ]) arry.append([ cur[0]-1, cur[1] ]) print(f"#{test_case} {result.. 2022. 12. 28.