For Programmer

11052번 문제하고 거의 동일한 문제이지만 11052와 비슷한 단순한 DP문제라고 생각하고 풀었기에 아무리 생각해도 답이 나오지 않아 이 문제를 풀지 못했다. 이러한 문제 유형의 핵심은 이것이다. N이 만약에 6이라고 생각하자. 그렇다면 N이 3일때 나올 수 있는 경우의 수(1+2,2+1,3)를 쭉 적어놓고 여기에+3만 해주면 6이 된다. 이와 마찬가지로 N이 4일때 나올 수 있는 횟수, N이 5일때 나올 수 있는 횟수 다 동일하게 적용이 된다. 이런식으로 점화식을 세워 쭉쭉 구해나가면 되는 것이다. 그렇다면 나올 수 있는 점화식이 이것이다. dp = [[0 for _ in range(3)] for _ in range(11)] #dp초기화 # 각각 1,2,3으로 끝나는 경우의 수 dp[1] = [1, ..

N = int(input()) P = [0] + list(map(int, input().split())) dp = [0] * (N + 1) dp[1] = P[1] for i in range(1, N + 1): for j in range(1, i + 1): if dp[i] 이 문제가 왜 DP로 풀 수 있냐면 1개부터 N개까지 개수마다 최대비용을 저장하고 그 다음 비용을 구할때 저장한 값을 가지고 활용을 할 수 있다는 것이다. 무슨말이나면 예를들어 1개를 살때의 최대값이 d..

코드 n = int(input()) dp = [0, 1, 3] # n이 2이하일때 횟수를 미리 초기화 if n > 2: for i in range(3, n + 1): dp = dp + [0] * (n - 2) dp[i] = (dp[i - 2] * 2) + dp[i - 1] print(dp[n] % 10007) -> 간단히 11726번과 비슷하게 점화식만 찾으면 된다. 그림을 그려서 n이 4일때와 5일때를 확인해보면 11과 21이 나온다. 5개 정도가 나오면 점화식을 찾을 수 있는데 (n-2)번째 * 2 + (n-1)번째 가 반복되는 것을 알 수 있다. * 그림을 직접 그리면서 확인해야 하다보니 4번째가 계속 10이 나와서 결국 답을 봤다. 시간도 오래걸리는 이런 노가다 문제...

입력 N 1 2 3 4 5 6 방법의 수 1 2 3 5 8 13 이 문제는 간단하게 첫번째 항과 2번째 항의 값이 3번째 항의 값과 같다 라는 점화식만 잘 찾으면 된다. 사실 타일에 들어가는 구성을 보고 이 점화식을 찾아야하는데 사실 dp문제라는걸 몰랐다면 이걸 찾는데 오래 걸릴꺼 같다는 생각을 했다. 코드1 (반복문 돌기전 미리 dp리스트를 n+1개 만큼 초기화) n = int(input()) dp = [0, 1, 2] # n이 2이하일때 횟수를 미리 초기화 if n > 2: # 만약 n이 3보다 크다면 dp = dp + ([0] * (n - 2)) # 반복문을 돌기 위해 그 이후의 n-2개를 dp배열에 추가해준다. for i in range(3, n + 1): # 3 부터 n 까지 점화식을 돈다. d..

코드 X = int(input()) dp = [0] * (X + 1) # 각 인덱스(1~X)마다 1을 만들기위한 연산 횟수를 저장할 DP배열 선언, # d[1] = 0 인이유는 1일때는 연산 횟수가 0이기 때문이다. # 2일때부터 n번째 일때까지 몇번을 시행해야하는지 체크 for i in range(2, X + 1): # -1 했을 때의 횟수 저장 dp[i] = dp[i - 1] + 1 # 일단 처음에 그 전에 시행했던 횟수(d[i-1])에서 +1 만해주면 되기 때문에 d[i] = 전의횟수(d[i-1]) + 1 # 3으로 나눴을 때의 횟수저장 if i % 3 == 0: dp[i] = min(dp[i], dp[i // 3] + 1) # 만약 3으로 나누어 진다면 6은 2일때의 횟수에서 + 1 만 하면 되기..

코드 import itertools # input n, m = map(int, input().split()) x_lst = [] for _ in range(n): x_lst.append(list(map(int, (input())))) # matrix 1d -> 2d convert(비트마스크를 입력받은 행렬과 같은 모양으로 변형) def bitmask_to_matrix(l, m): return [l[i:i + m] for i in range(0, len(l), m)] # itertools의 product를 이용해서 비트마스크 제너레이터 만들기 # e.g) (0,0,0,0), (0,0,0,1) ... (1,1,1,1) 0,1 을 reapeat개수만큼 반복해서 뽑아준다. bitmask = itertools.p..

코드1(라이브러리 이용) import itertools N, S = map(int, input().split()) array = list(map(int, input().split())) count = 0 for i in range(1, N + 1): for j in itertools.combinations(array, i): if sum(j) == S: count += 1 print(count) -> 워낙 쉬운 코드라 설명은 생략했다. 조합 라이브러리를 이용하면 알아서 원하는 개수만큼 원소를 뽑아주므로 반복문을 돌면서 i값을 뽑는 개수로 이용하였다. 코드2(dfs(재귀)이용) N, S = map(int, input().split()) array = list(map(int, input().split()))..

코드1(라이브러리 이용) import itertools while True: array = list(map(int, input().split())) k = array[0] S = array[1:] for i in itertools.combinations(S, 6): print(*i) if k == 0: exit() print() -> 따로설명은 생략하겠다. 조합 라이브러리를 사용하게 허용해놓아서 사실상 배열에 k값도 들어가있기 때문에 k값이랑 로또 번호하고 분리만 해주면 쉽게 풀수 있는 문제이다. 코드2(재귀 이용) def dfs(depth, idx): if depth == 6: print(*out) return for i in range(idx, k): out.append(S[i]) dfs(depth ..