목록Python/알고리즘(Python) (28)
일기 대신 코드 슬쩍
10. 다이나믹 프로그래밍(바닥 공사)
# 바닥 공사 n = int(input()) d = [0] * (n+1) d[1] = 1 d[2] = 3 for i in range(3,n+1): d[i] = 2*d[i-2] + d[i-1] print(d[n] % 796796) Uploaded by Notion2Tistory v1.1.0
# 효율적인 화폐 구성 n, m = map(int,input().split()) money = [] for _ in range(n): money.append(int(input())) # Step 0(초기화) # 각 인덱스에 해당하는 값으로 INF의 값을 설정 # 이는 특정 금액을 만들 수 있는 화폐구성이 가능하지 않다는 의미를 가짐 d = [10001] * (m+1) d[0] = 0 # Step 1 # 첫번째 화폐 단위 money[0]를 확인 for i in money: for j in range(i, m+1): if d[j-i] != 10001: d[j] = min(d[j], d[j-i]+1) if d[m] == 10001: print(-1) else: print(d[m]) Uploaded by Not..
# 개미전사 n = int(input()) k = list(map(int, input().split( ))) d = [0] * 100 d[0] = k[0] d[1] = max(k[0],k[1]) for i in range(2,n): d[i] = max(d[i-1],d[i-2] + k[i]) print(d[n-1]) Uploaded by Notion2Tistory v1.1.0
10. 다이나믹 프로그래밍(1로 만들기)
# 1로 만들기 x = int(input()) d = [0] * 30001 for i in range(2, x+1): d[i] = d[i-1] + 1 if i % 2 == 0: d[i] = min(d[i],d[i//2]+1) if i % 3 == 0: d[i] = min(d[i],d[i//3]+1) if i % 5 == 0: d[i] = min(d[i],d[i//5]+1) print(d[x]) Uploaded by Notion2Tistory v1.1.0
# 성적이 낮은 순서로 학생 출력하기 N = int(input()) grade = {} for _ in range(N): name, score = input().split() grade[score] = name grade = dict(sorted(grade.items())) for i in grade.values(): print(i, end = ' ') Uploaded by Notion2Tistory v1.1.0
8. 정렬(위에서 아래로)
# 위에서 아래로 N = int(input()) numList = [] for _ in range(N): numList.append(int(input())) numList.sort(reverse= True) for i in numList: print(i,end=' ') Uploaded by Notion2Tistory v1.1.0
# 두 배열의 원소 교체(예시) A = [1,2,5,4,3] B = [5,5,6,6,5] N = 5 K = 3 A.sort() B.sort(reverse= True) for i in range(K): if A[i] < B[i]: A[i] = B[i] print(sum(A))# 두 배열의 원소 교체 N, K = map(int, input().split( )) A = list(map(int, input().split( ))) B = list(map(int, input().split( ))) A.sort() B.sort(reverse= True) for i in range(K): if A[i] < B[i]: A[i] = B[i] else: # 없는 경우 시간 복잡도를 줄이기 위해 반복문 탈출 break pri..
# 감시 피하기 from itertools import combinations n = int(input()) board = [] teachers = [] spaces = [] for i in range(n) : board.append(list(input().split())) for j in range(n) : if board[i][j] == 'T' : teachers.append((i, j)) if board[i][j] == 'X' : spaces.append((i, j)) def watch(x, y, direction) : if direction == 0 : while y >= 0 : if board[x][y] == 'S' : return True if board[x][y] =='O' : return ..