국문과 유목민

1. 문제 설명 몇 개의 화폐와 TargetNumber 주어진다. 해당 화폐를 가지고 주어진 수를 만들기 위한 최소한의 경우를 구하라. - df에 만들 수 있는 최소의 경우의 수를 찾는다. 덧셈으로 값이 구성이 된다.따라서 들어오는 array마다 조건이 달라질 것이다. - 값이 증가하지 않는다면 -1을 넣어야 하지만 최소의 경우의 수를 구해야 하기 때문에 큰 금액을 넣어준다. 2. 코드 # 입력 n, m = list(map(int, input().split())) array = [] for i in range(n): array.append(int(input())) money = list(set(array)) """ 2 15 2 3 """ # DP df = [10001]*(m+1) df[0] = 0 # 값..

1. 문제 설명 2 x i 형태의 가로로 긴 타일의 바닥공사를 하려고 한다. 타일의 종류가 1 X 2 / 2 X 1 / 2 X 2 3개일 때, 타일을 까는 경우의 수는 총 몇 개인가? - 문제의 범위가 정해져있었기 때문에 해당 범위까지만 고려하면 된다. - 점화식을 만들기 전의 값인 1, 2일 때의 값은 직접 구해줘야 한다. - i-1일 때 놓을 수 있는 경우의 수는 1개 - i-2일 때 놓을 수 있는 경우의 수는 2개 2. 코드 n = int(input()) df=[0]*(n+1) df[1] = 1 df[2] = 3 for i in range(3, n+1): df[i] = (df[i-1]+(df[i-2]*2))%796796 # 문제의 조건 print(df[i]) """ 4 11 > 리스트 값: [0, ..

1. 문제 설명 - 개미가 배짱이네 집을 털러가는데 연속된 방을 털 수가 없다. 따라서 한 칸 을 넘어서 털어야 하는데 그럴 경우 가장 많이 털었을 때의 값을 묻는 문제 2. 코드 n = 4 array = list(map(int, "1 3 1 5".split())) df = [0]*(n) df[0] = array[0] df[1] = max(array[0], array[1]) for i in range(2, n): df[i] = max(df[i-1], df[i-2]+array[i]) df[n-1] # >> 8 3. 코멘트 - 항상 최선의 선택을 한다는 것을 알아둬야 한다. - 이전의 선택에 대한 계산 정보는 해당 위치에 저장이 된다. - 여기서 하나 신경써야할 점은 계산을 안하고 이전에 사용된 값을 그대로..

1. 문제 설명 - 주어진 수를 1로 만들기 위해 수행해야 하는 연산의 횟수를 구하는 문제 - 2, 3, 5를 나누는 연산이 존재 2. 코드 n = int(input()) df = [0]*(n+1) for i in range(2, n+1): df[i] = df[i-1]+1 if i%2==0: df[i] = min(df[i], df[i//2]+1) elif i%3==0: df[i] = min(df[i], df[i//3]+1) elif i%5==0: df[i] = min(df[i], df[i//5]+1) print(df[n]) """ 6 >> 2 """ 3. 코멘트 - 코드는 간단했으나 횟수 추가 부분을 이해하는데 시간이 좀 걸렸었다. - 문제 풀이 방식이 DP였다는 것을 생각해서 이해를 했던 것 같다.