bong-u/til

bong-u/til

🏠 home 🐈 repository

백준 - 2748 : 피보나치 수2 (B2)

🧠 Algorithm

“알고리즘 분류-DP"에서 안 푼 문제이길래 한 번 풀어봤다. 1N = int(input()) 2 3L = [0, 1] + [0]*89 4 5for i in range(2, N+1): 6 L[i] = L[i-1]+L[i-2] 7 8print (L[N])

백준 - 2573 : 빙산 (G5)

🧠 Algorithm

1import copy 2from collections import deque 3 4N, M = map(int, input().split()) 5L = [list(map(int, input().split())) for _ in range(N)] 6L[0][0] = 0 7L[N-1][M-1] = 0 8vx = [0, 0, -1, 1] 9vy = [-1, 1, 0, 0] 10 11def melt(L): 12 L_ = copy.deepcopy(L) 13 for i in range(M): 14 for j in range(N): 15 if L[j][i] != 0: 16 for k in range(4): 17 nx = j + vx[k] 18 ny = i + vy[k] 19 20 if not 0 <= nx < N or not 0 <= ny < M: 21 continue 22 if L[nx][ny] == 0 and L_[j][i] !

백준 - 2565 : 전깃줄 (G5)

🧠 Algorithm

1N = int(input()) 2L = [list(map(int, input().split())) for _ in range(N)] 3L = [i[1] for i in sorted(L)] 4dp = [0]*N 5for i in range(N): 6 dp[i] = 1 7 for j in range(i): 8 if L[j] < L[i]: 9 dp[i] = max(dp[i], dp[j]+1) 10 11print (N-max(dp)) LIS를 이용하는 문제

백준 - 2294 : 동전 2 (G5)

🧠 Algorithm

1N, K = map(int, input().split()) 2V = [] 3for _ in range(N): 4 V.append(int(input())) 5dp = [[0]+([10001]*K) for _ in range(N+1)] 6 7for i in range(1, N+1): 8 for j in range(1, K+1): 9 if j >= V[i-1]: 10 dp[i][j] = min(dp[i-1][j], dp[i][j-V[i-1]]+1) 11 else: 12 dp[i][j] = dp[i-1][j] 13 14res = dp[N][K] 15 16print (res if res != 10001 else -1) dp를 많이 풀어보자

백준 - 2225 - 합분해 (G5)

🧠 Algorithm

1N, K = map(int, input().split()) 2 3dp = [[0]*(N+1) for _ in range(K+1)] 4for i in range(1, K+1): 5 dp[i][0] = 1 6 7for i in range(1, K+1): 8 for j in range(1, N+1): 9 dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000000000 10print (dp[K][N]) 내 힘으로 풀었다!

백준 - 2193 : 이친수 (S3)

🧠 Algorithm

1N = int(input()) 2dp = [1]*N 3for i in range(2, N): 4 dp[i] = dp[i-2]+dp[i-1] 5print (dp[N-1]) 피보나치였다

백준 - 17404 : RGB거리 2 (G4)

🧠 Algorithm

1N = int(input()) 2L = [list(map(int, input().split())) for _ in range(N)] 3 4result = 100000 5 6for i in range(3): 7 dp = [[0, 0, 0] for _ in range(N)] 8 dp[0] = [10000]*3 9 dp[0][i] = L[0][i] 10 for j in range(1, N): 11 dp[j][0] = min(dp[j-1][1], dp[j-1][2])+L[j][0] 12 dp[j][1] = min(dp[j-1][0], dp[j-1][2])+L[j][1] 13 dp[j][2] = min(dp[j-1][0], dp[j-1][1])+L[j][2] 14 15 dp[N-1][i] = 100000 16 result = min([result]+dp[N-1]) 17 18print (result) 인터넷을 참고하여 풀었다

백준 - 1699 : 제곱수의 합 (S2)

🧠 Algorithm

1N = int(input()) 2 3dp = [100000]*(N+1) 4tmp = 1 5 6for i in range(1, N+1): 7 if i**(1/2) % 1 == 0: 8 dp[i] = 1 9 tmp += 1 10 else: 11 for j in range(1, tmp): 12 dp[i] = min(dp[i], dp[i-(j**2)]+1) 13 14print (dp[N])

백준 - 15683 : 감시 (G4)

🧠 Algorithm

1import copy, sys 2 3N, M = map(int, input().split()) 4L = [list(map(int, input().split())) for _ in range(N)] 5cctv = [] 6direction = [[[(0, 1)], [(0, -1)], [(1, 0)], [(-1, 0)]], 7[[(-1, 0), (1, 0)], [(0, -1), (0, 1)]], 8[[(-1, 0), (0, -1)], [(0, -1), (1, 0)], [(1, 0), (0, 1)], [(0, 1), (-1, 0)]], 9[[(-1, 0), (0, -1), (1, 0)], [(0, -1), (1, 0), (0, 1)], [(1, 0), (0, 1), (-1, 0)], [(0, 1), (-1, 0), (0, -1)]], 10[[(-1, 0), (0, -1), (1, 0), (0, 1)]]] 11res = sys.

백준 - 14891 : 톱니바퀴 (G5)

🧠 Algorithm

1from collections import deque 2 3wheels = [deque(map(int, list(input()))) for _ in range(4)] 4 5def rotate(wheel, direction): 6 if direction == 1: 7 wheel.appendleft(wheel.pop()) 8 else: 9 wheel.append(wheel.popleft()) 10 return wheel 11 12K = int(input()) 13vd = [1, -1] 14res = 0 15 16for _ in range(K): 17 N, D = map(int, input().split()) 18 q = deque() 19 q.append((N-1, D)) 20 visited = [False] * 4 21 tmp = [] 22 23 while q: 24 cur, curD = q.

백준 - 11057 : 오르막 수 (S1)

🧠 Algorithm

1N = int(input()) 2dp = [[1]+[0]*9 for _ in range(N+1)] 3 4for i in range(1, N+1): 5 for j in range(1, 10): 6 dp[i][j] = dp[i-1][j]+dp[i][j-1] 7 8print (sum(dp[N])%10007)

백준 - 11052 : 카드 구매하기 (S1)

🧠 Algorithm

1N = int(input()) 2P = list(map(int, input().split())) 3 4D = [P[0]]+[0]*(N-1) 5 6for i in range(1, N): 7 for j in range(1, i+1): 8 D[i] = max(D[i-j]+P[j-1], D[i]) 9 D[i] = max(P[i], D[i]) 10 11print (D[N-1]

백준 - 11051 : 이항계수2 (S2)

🧠 Algorithm

내장 함수 사용 1import math 2 3N, K = map(int, input().split()) 4 5print (math.comb(N, K)%10007 파스칼의 사각형? dp 구현 1N, K = map(int, input().split()) 2 3if K == 0: 4 print(1) 5 exit() 6 7dp = [[0]*N for _ in range(K)] 8 9for i in range(N): 10 dp[0][i] = i+1 11 12for i in range(1, K): 13 for j in range(i, N): 14 dp[i][j] = (dp[i-1][j-1] + dp[i][j-1]) % 10007 15 16print (dp[K-1][N-1])

백준 - 11048 : 이동하기 (S2)

🧠 Algorithm

1N, M = map(int, input().split()) 2dp = [list(map(int, input().split())) for _ in range(N)] 3 4for i in range(1, N): 5 dp[i][0] = dp[i][0]+dp[i-1][0] 6for i in range(1, M): 7 dp[0][i] = dp[0][i]+dp[0][i-1] 8 9for i in range(1, N): 10 for j in range(1, M): 11 dp[i][j] = dp[i][j]+max(dp[i-1][j], dp[i][j-1]) 12 13print (dp[N-1][M-1])

백준 - 10844 : 쉬운 계단 수 (S1)

🧠 Algorithm

접근이 어려워 인터넷을 참고했다. 코드는 보지 않았다. 수의 길이가 i이면서 마지막 숫자가 j인 계단 수의 개수를 저장하는 것이 핵심이다. 점화식은 L[i][j] = L[i-1][j-1]+L[i-1][j+1] 이다. 1N = int(input()) 2L = [[0]*12 for _ in range(100)] 3L[0] = [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] 4 5for i in range(1, N): 6 for j in range(1, 11): 7 L[i][j] = L[i-1][j-1]+L[i-1][j+1] 8 9print (sum(L[N-1])%1000000000)

백준 - 1010 : 다리놓기 (S5)

🧠 Algorithm

1import math 2 3for _ in range(int(input())): 4 a, b = map(int, input().split()) 5 print(math.comb(max(a,b), min(a,b)))

백준 - 9655 : 돌게임 (S5)

🧠 Algorithm

1N = int(input()) 2print ('CY' if N%2==0 else 'SK') 게임이론에서 기초 중 기초 문제이다

백준 - 1309 : 동물원 (S1)

🧠 Algorithm

1N = int(input()) 2dp = [1, 3] + [0]*(N-1) 3 4for i in range(2, N+1): 5 dp[i] = (dp[i-1]*2 + dp[i-2]) % 9901 6 7print(dp[N]) 고민 끝에 답을 찾아보긴 했다 점화식 생각해내는 놈들 머리에 뭐가 든건지 모르겠다

백준 - 1890 : 점프 (S1)

🧠 Algorithm

1N = int(input()) 2 3L = [list(map(int, input().split())) for _ in range(N)] 4dp = [[0]*N for _ in range(N)] 5dp[0][0] = 1 6for i in range(N): 7 for j in range(N): 8 if L[i][j] == 0: 9 continue 10 if dp[i][j] != 0: 11 right = j+L[i][j] 12 bottom = i+L[i][j] 13 14 if right < N: 15 dp[i][right] += dp[i][j] 16 if bottom < N: 17 dp[bottom][j] += dp[i][j] 18print (dp[N-1][N-1]) dp에 있는 값을 더해야하는데 1을 더해서 몇 번 틀렸다 거의 혼자 힘으로 풀었다

백준 - 2096 : 내려가기 (G5)

🧠 Algorithm

1N = int(input()) 2L = [list(map(int, input().split())) for _ in range(N)] 3dp1 = [L[0][i] for i in range(3)] 4dp2 = [L[0][i] for i in range(3)] 5 6for i in range(1, N): 7tmp1 = [0]*3 8tmp2 = [0]*3 9for j in range(3): 10 11 if j == 0: 12 tmp1[0] = L[i][j] + max(dp1[0], dp1[1]) 13 tmp2[0] = L[i][j] + min(dp2[0], dp2[1]) 14 elif j == 1: 15 tmp1[1] = L[i][j] + max(dp1[0], dp1[1], dp1[2]) 16 tmp2[1] = L[i][j] + min(dp2[0], dp2[1], dp2[2]) 17 else: 18 tmp1[2] = L[i][j] + max(dp1[1], dp1[2]) 19 tmp2[2] = L[i][j] + min(dp2[1], dp2[2]) 20 dp1 = [i for i in tmp1] 21 dp2 = [i for i in tmp2] 22 23print (max(dp1), min(dp2)) Memoization과정이 다른 memoization 변수에 대해 종속적이라면 잘못된 결과를 초래한다 위 코드에서는 이를 방지하기 위해 tmp1, tmp2 변수를 사용한다 깊이 생각하지 않고 여러 번 제출해서 WA개수가 조금 많다;;

4
5
6
7
8