종식당

문제 설명 N을 입력받고 2xN 크기의 바닥을 위 3가지 종류의 덮개로 채워야 할 때의 경우의 수를 출력하면 된다. 위를 참고하여 점화식을 유도해낸다음 코드에 적용시키면 된다. 문제 코드 N = int(input()) dp = [0]*(N+1) dp[1] = 1 #2x1 짜리 하나 총 1가지 dp[2] = 3 #2x1 짜리 두개,1x2 짜리 두개, 2x2 짜리 하나 총 3가지 for i in range(3,N+1): dp[i] = (dp[i-1] + 2*dp[i-2]) % 796796 print(dp[N]) 점화식만 문제를 보고 뽑을 줄 알고 초기 설정만 잘해주면 어렵지 않게 dp문제를 풀 수 있을 것 같다. 관련 문제 https://www.acmicpc.net/problem/11726 11726번: 2..

문제 설명 다이내믹 프로그래밍의 가장 기본적인 문제이다. 입력으로 받은 정수 x를 5로 나누기, 3으로 나누기, 2로 나누기, 1을 빼기 이 4가지 경우의 수를 조합해 최소한의 연산으로 1로 만드는 연산의 횟수를 출력하면 된다. 문제 코드 X = int(input()) dp = [0] * (X+1) for i in range(2,X+1): dp[i] = dp[i-1]+1 # 1 뺏을 때 if i%2 == 0: dp[i] = min(dp[i],dp[i//2]+1) # 2로 나누었을 때 if i%3 == 0: dp[i] = min(dp[i],dp[i//3]+1) # 3으로 나누었을 때 if i%5 == 0: dp[i] = min(dp[i],dp[i//5]+1) # 5로 나누었을 때 print(dp[X]) 일..

문제 설명 첫 번째 줄에 떡의 개수 N과 떡의 길이 M이 주어지고 두 번째 줄에 떡들의 길이가 주어지면 이들을 각각 잘라서 M만큼 길이의 떡을 얻기 위한 절단기의 최댓값을 출력하면 된다. 문제 풀이 문제 코드 N, M = map(int,input().split()) lst = list(map(int,input().split())) start = 0 end = max(lst) result = 0 while start mid: total+=i-mid if total < M: end = mid - 1 else: result = mid start = mid + 1 print(result) 이 문제는 이진 탐색을 생각해 내서 접근하기는 너무 어려운 문제였고 이진 탐색이라는 알고리즘을 알아도 적용하기 너무 어려워 ..

문제 설명 첫 번째 줄에 N을 입력받고 두 번째 줄에 N개의 부품을 입력받는다. 세 번째 줄에 M을 입력받고 네 번째 줄에 N개의 부품을 입력받은 후 N개의 부품이 M개 부품에 포함되는지 판단하여 포함되면 yes 안되면 no를 출력하면 된다. 개념 설명 문제를 풀기 전에 먼저 이진 탐색의 개념을 잡고 넘어가려 한다. 이진 탐색이란, 오름차순으로 정렬된 배열을 반복적으로 반으로 나누어 target이 선택될 때까지 탐색하는 알고리즘이다. 이때 이진 탐색을 사용할 때는 꼭 정렬된 상태에서 사용할 수 있다는 점을 기억해두자! 시간 복잡도는 O(logn)이다. 1. 반복문 사용 def binary_search(target, data): data.sort() start = 0 # 맨 처음 위치 end = len(d..

문제 설명 문제는 크게 어렵지 않다. 8x8 좌표평면을 체스판이라고 생각하고 출발 지점이 입력으로 들어오면 그 지점부터 체스판에서 나이트가 움직일 수 있는 경우의 수를 출력하면 된다. 1번과 2번을 나누어서 생각한 경우의 수는 위와 같다. 저렇게 총 8가지의 경우의 수가 존재한다. 이제 시작 지점에서 칸 밖을 안 나가는 지만 생각해 주면 된다. 문제 코드 N = input() row = int(N[1]) column = int(ord(N[0])) - ord('a') + 1 steps = [(1,2),(-1,2),(1,-2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)] result = 0 for step in steps: new_row = row + step[0] new_column ..