모눈종이에 사각사각

🍎 [백준 1654] 랜선 자르기 문제링크 https://www.acmicpc.net/problem/1654 이전에 풀었던 2805번 나무 자르기 문제와 굉장히 유사한 문제였다. ⚾ 코드 import sys k, n = map(int, input().split()) array = [int(sys.stdin.readline()) for _ in range(k)] start = 1 end = max(array) while start

🍎 [백준 2805] 나무 자르기 문제링크 https://www.acmicpc.net/problem/2805 ⚾ 코드(pypy3) import sys input = sys.stdin.readline n, m = map(int, input().split()) tree = list(map(int, input().split())) end = max(tree) start = 0 while start mid: remain += i-mid if remain < m: end = mid-1 else: start = mid+1 print(end) 🔔 해결 과정 & 깨달은 점 - 해당 문제는 전형적인 이진탐색 문제이다. - 입력 값이 20억이므로 이진 탐색을 시도해보자. - 처음에 cm가 아닌, 인덱스의 중앙값으로 시도를..

🍎 [백준 2294] 동전2 문제 링크 https://www.acmicpc.net/problem/2294 ⚾ 코드 코드 1 n, k = map(int, input().split()) dp = [100001]*100001 coins = [int(input()) for _ in range(n)] coins.sort() for coin in coins: for now in range(1, k+1): if now % coin != 0: dp[now] = min(dp[now], dp[now-coin]+1) else: dp[now] = min(dp[now], now//coin) if dp[k] == 100001: print(-1) else: print(dp[k]) 코드 2 n, k = map(int, input()..

🍎 [백준 11727] 2×n 타일링 2 문제링크 https://www.acmicpc.net/problem/11727 ⚾ 코드 n = int(input()) dp = [0]*(n+1) dp[1] = 1 dp[2] = 3 for i in range(3, n+1): dp[i] = (dp[i-1]+(dp[i-2]*2)) % 10007 print(dp[n]) 🔔 해결 과정 & 깨달은 점 - 다음은 내가 문제를 풀면서 생각한 아이디어 이다. - 각 N은 (이전(N-1)의 경우의 수 + 2*1 타일 추가한 것) + (전전(N-2)의 경우의 수 + 2*2 타일 또는 2*1 타일 2개 추가한 것) 으로 이루어져 있다. - 새로 추가하는 타일 이외의 경우의 수는 이전의 N의 경우의 수에 포함되어 있기 때문에 따로 생각하..