Jimangogo

'오르막 수' 코드1 n = int(input()) d = [[0 for i in range(10)] for i in range(n+1)] d[1] = [1 for i in range(10)] if n > 1: d[2] = [i for i in range(10, -1, -1)] for i in range(3, n+1): for j in range(10): temp = 0 for k in range(j): temp += d[i-1][k] d[i][j] = sum(d[i-1]) - temp print(sum(d[n]) % 10007) 풀이 dp테이블을 위와 같은 표처럼 2차원으로 구현했다. 블로그 포스팅을 위해 표를 그리다보니 처음에 생각했던 점화식은 d[i][2] = sum(d[i-1]) - (d[i-1]..

'카드 구매하기' 코드 n = int(input()) array = [0] + list(map(int, input().split())) d = [0 for i in range(n+1)] for i in range(n+1): d[i] = array[i] for i in range(n+1): for j in range(i+1): d[i] = max(d[i], d[i-j] + d[j]) print(d[n]) 풀이 1. 자기자신이 max인 경우도 있기 때문에 dp테이블 d를 array로 초기화해준다. 2. 앞에서부터 자기자신까지 모든 경우의 수를 살펴보며 max인 것을 찾는다. comment 코드는 굉장히 단순한데 이해하기가 너무 어려웠다. 별거 아닌거같았는데 dp문제는 항상 내 뒤통수를 친다. 그리고 dp문제..

'카드 정렬하기' 문제 입력 출력 코드 import sys from queue import PriorityQueue n = int(input()) array = PriorityQueue() for i in range(n): array.put(int(sys.stdin.readline())) result = [] while array.qsize() >= 2: temp = array.get(0) + array.get(1) result.append(temp) array.put(temp) if n == 1: print(0) else: print(sum(result)) 풀이 1. 입력받는 카드 묶음의 크기 배열을 빠르게 정렬하기 위해 우선순위 큐로 선언한다. 2. 비교횟수를 저장할 배열 result를 선언한다. 3..

'산업 스파이의 편지' 문제 입력 출력 코드 from itertools import permutations import math num = 9999999 # 종이조각 수가 최대 7개이고 가장 큰 숫자가 9이므로 소수 판별 최댓값은 9999999로 설정 prime = [True for i in range(num+1)] # 해당 숫자(인덱스)가 소수라면 True, 소수가 아니라면 False를 넣을 배열 for i in range(2, int(math.sqrt(num)+1)): # 에라스토테네스의 체(2부터 num의 제곱근까지 반복) if prime[i]: j = 2 while i*j

'행렬' 문제 입력 출력 코드 n, m = map(int, input().split()) A = [] B = [] for i in range(n): A.append(list(input())) for i in range(n): B.append(list(input())) def change(x, y): # 3*3 행렬 뒤집는 연산 함수 # 지정한 인덱스의 3*3 행렬이 범위를 넘지 않을 경우에 for문 돌기 if x < n and x+1 < n and x+2 < n and y < m and y+1 < m and y+2 < m: for i in range(x, x+3): for j in range(y, y+3): if A[i][j] == '1': A[i][j] = '0' else: A[i][j] = '1' c..