Jinho Tech

백준 알고리즘 16395번 파스칼의 삼각형(python)

기본적인 다이나믹 프로그래밍 문제이다. n, k = map(int, input().split()) li = [[1], [1, 1]] for i in range(2, n): t = [1] for j in range(1, i): t.append(li[i-1][j-1]+li[i-1][j]) t.append(1) li.append..

jinho-study.tistory.com

백준 알고리즘 15489번 파스칼 삼각형(python)

기본적인 다이나믹 프로그래밍 문제이다. R, C, W = map(int, input().split()) li = [[1], [1, 1]] for i in range(2, R+W-1): t = [1] for j in range(1, i): t.append(li[i-1][j-1]+li[i-1][j]) t.append(1) li..

jinho-study.tistory.com

백준 알고리즘 2670번 연속부분최대곱(python)

기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) li = [float(input()) for _ in range(N)] t = [0]*(N) t[0] = li[0] for i in range(1, N): if t[i] == 0: t[i] = max(li[i], li[i]*t[i-1]) print("%...

jinho-study.tistory.com

백준 알고리즘 1149번 RGB거리(python)

기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) li = [list(map(int, input().split())) for _ in range(N)] for i in range(1, N): for j in range(3): li[i][j] += min(li[i-1][:j]+li[i-1][j+1:]) p..

jinho-study.tistory.com

백준 알고리즘 11053번 가장 긴 증가하는 부분 수열(python)

아주 기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) A = list(map(int, input().split())) dp = [1]*N for i in range(1, N): for j in range(i): if A[j] < A[i]: dp[i] = max(dp[i], dp[j]+1) print..

jinho-study.tistory.com

백준 알고리즘 1003번 피보나치 함수(python)

기본적인 다이나믹 프로그래밍 문제이다. EX) 입력이 3일 때, 1의 결과 (0, 1)과 2의 결과 (1, 1)을 더한 (1, 2)가 답이다. 피보나치수열의 2차원 버전이 아닐까 라는 생각이 든다. 리스트를 그대로 출력

jinho-study.tistory.com

백준 알고리즘 1904번 01타일(python)

기본적인 다이나믹 프로그래밍 문제이다. N = 1 -> 1개, N = 2 -> 2개, N = 3 -> 3개, N = 4 -> 5개, N = 5 -> 8개... 규칙을 보면 1, 2, 3, 5, 8, 13 ...인데 피보나치 수열이다. a, b = 1, 1 for i in range(int..

jinho-study.tistory.com

백준 알고리즘 1932번 정수삼각형(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) li = [list(map(int, input().split())) for i in range(n)] if n > 1: li[1][0] += li[0][0] li[1][1] += li[0][0] for i in range(2, n): for j in ra..

jinho-study.tistory.com

백준 알고리즘 1912번 연속합(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) li = list(map(int, input().split())) for i in range(1, n): li[i] = max(li[i], li[i]+li[i-1]) print(max(li))

jinho-study.tistory.com

백준 알고리즘 1463번 1로 만들기(python)

기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) li = [1000001]*(N+1) li[1] = 0 for i in range(1, N+1): if i%3 == 0: li[i] = min(li[i], li[i//3]+1) if i%2 == 0: li[i] = min(li[i], li[i//2]+1)..

jinho-study.tistory.com

백준 알고리즘 9461번 파도반 수열(python)

기본적인 다이나믹 프로그래밍 문제이다. 2가지 패턴으로 풀어봤는데 아래쪽이 좀 더 합리적인 것 같다. li = [0, 1, 1, 1, 2, 2, 3] i = 7 while i <= 100: li.append(li[-1] + li[i-5]) i += 1 for _ in range(i..

jinho-study.tistory.com

백준 알고리즘 9184번 신나는 함수 실행(python)

기본적인 다이나믹 프로그래밍 & 재귀 문제이다. dp = [[[0]*21 for a in range(21)] for b in range(21)] def w(a, b, c): if a <= 0 or b <= 0 or c <= 0: return 1 if a > 20 or b > 20 or c > 20: return w(20..

jinho-study.tistory.com

백준 알고리즘 2579번 계단 오르기(python)

기본적인 다이나믹 프로그래밍 문제이다. li와 dp를 미리 선언하고 풀어야 런타임 에러가 안 나온다. 마지막 계단의 전 계단을 밟은 경우와, 밟지 않은 경우 2가지를 고려해서 풀면 된다. N = int(inp

jinho-study.tistory.com

백준 알고리즘 9095번 1, 2, 3 더하기(python)

기본적인 다이나믹 프로그래밍 문제이다. for _ in range(int(input())): n = int(input()) dp = [0]*12 dp[0] = dp[1] = 1 dp[2] = 2 for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] print(dp[n])

jinho-study.tistory.com

백준 알고리즘 11726번 2×n 타일링(python)

기본적인 다이나믹 프로그래밍 문제이다. 두 가지 경우만 고려하면 쉽게 풀 수 있다. 1. 2*(n-1) -> 2*n: 타일이 한 개 들어가는 경우밖에 없기 때문에 2*(n-1) 크기의 직사각형에 타일을 배치하는 방

jinho-study.tistory.com

백준 알고리즘 11727번 2×n 타일링 2(python)

기본적인 다이나믹 프로그래밍 문제이다. 11726번 2×n 타일링과 비슷한 문제이다. n = int(input()) dp = [0, 1, 3] for i in range(3, n+1): dp.append(dp[i-2]*2+dp[i-1]) print(dp[n]%10007)

jinho-study.tistory.com

백준 알고리즘 9625번 BABBA(python)

기본적인 다이나믹 프로그래밍 문제이다. 처음에 풀 때 dp에 문자열(EX: "BA")을 저장했는데 메모리 초과가 나와서 그냥 숫자로 해결했다. k = int(input()) dp = [0]*(k+1) dp[1] = 1 for i in range(2, k+1): dp..

jinho-study.tistory.com

백준 알고리즘 13301번 타일 장식물(python)

기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) dp = [0]*(N+1) dp[1] = 4 dp[2] = 6 for i in range(3, N+1): dp[i] = dp[i-1]+dp[i-2] print(dp[N])

jinho-study.tistory.com

백준 알고리즘 14916번 거스름돈(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) dp = [-1]*(n+1) dp[0] = 0 for i in range(1, n+1): if i >= 2 and dp[i-2] > -1: dp[i] = (dp[i-2]+1) if dp[i] == -1 else min(dp[i-2]+1, dp[i]) if..

jinho-study.tistory.com

백준 알고리즘 19947번 투자의 귀재 배주형(python)

브루트포스 알고리즘 & 다이나믹 프로그래밍 문제이다. H, Y = map(int, input().split()) dp = [0]*(Y+1) dp[0] = H for i in range(1, Y+1): if i-1 >= 0 and dp[i-1]: dp[i] = max(int(dp[i-1]*1.05), dp[i]) i..

jinho-study.tistory.com

백준 알고리즘 8394번 악수(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) a, b = 1, 0 for i in range(n): a, b = (a+b)%10, a%10 print(a)

jinho-study.tistory.com

백준 알고리즘 9844번 Gecko(python)

기본적인 다이나믹 프로그래밍 문제이다. h, w = map(int, input().split()) li = [list(map(int, input().split())) for _ in range(h)] dp = [[0]*w for _ in range(h)] dp[0] = li[0] for i in range(1, h): fo..

jinho-study.tistory.com

백준 알고리즘 13699번 점화식(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) dp = [0]*(36) dp[0] = 1 dp[1] = 1 dp[2] = 2 for i in range(3, n+1): t = 0 if i%2: for j in range(i//2): t += 2*dp[j]*dp[i-j-1] dp[i] = t + dp[..

jinho-study.tistory.com

백준 알고리즘 14606번 피자 (Small)(python)

간단한 수학 & 다이나믹 프로그래밍 문제이다. 평범하게 다이나믹 프로그래밍으로 풀면 아래 코드와 같다. N = int(input()) dp = [0]*(11) dp[1] = 0 dp[2] = 1 for i in range(3, N+1): m = i//2 dp[i] = m*(i-m..

jinho-study.tistory.com

백준 알고리즘 2193번 이친수(python)

기본적인 다이나믹 프로그래밍 문제이다. 평범하게 다이나믹 프로그래밍으로 풀면 아래 코드와 같다. 마지막 자리가 0인 숫자 뒤에는 0과 1 2개를, 마지막 자리가 1인 숫자는 0 1개를 추가할 수 있

jinho-study.tistory.com

백준 알고리즘 9507번 Generations of Tribbles(python)

기본적인 다이나믹 프로그래밍 문제이다. def koong(n): if n < 2: return 1 if n == 2: return 2 if n == 3: return 4 if dp[n]: return dp[n] dp[n] = koong(n-1) + koong(n-2) + koong(n-3) + koong(n-4) retur..

jinho-study.tistory.com

백준 알고리즘 14495번 피보나치 비스무리한 수열(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) dp = [1]*117 for i in range(4, n+1): dp[i] = dp[i-3] + dp[i-1] print(dp[n])

jinho-study.tistory.com

백준 알고리즘 15624번 피보나치 수 7(python)

기본적인 다이나믹 프로그래밍 문제이다. dp 리스트를 만들어서 풀면 메모리 초과가 나오고 그냥 a, b 변수 2개를 사용해서 풀면 시간 초과가 나오길래 뭔가 했는데, 너무 큰 숫자들로 계산하는

jinho-study.tistory.com

백준 알고리즘 17175번 피보나치는 지겨웡~(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) if n < 2: print(1) else: a, b = 1, 1 for i in range(n-1): a, b = a+b+1, a print(a%1000000007)

jinho-study.tistory.com

백준 알고리즘 11660번 구간 합 구하기 5(python)

누적 합 & 다이나믹 프로그래밍 문제이다. 처음에는 아래 코드와 같이 풀었다. PyPy3로 제출해야 통과가 된다. import sys N, M = map(int, sys.stdin.readline().split()) li = [list(map(int, sys.stdin.readlin..

jinho-study.tistory.com

백준 알고리즘 12852번 1로 만들기 2(python)

다이나믹 프로그래밍 or 그래프 탐색 문제이다. 다이나믹 프로그래밍 풀이 N = int(input()) dp = [[0, []] for _ in range(N+1)] dp[1][0] = 0 dp[1][1] = [1] for i in range(2, N+1): dp[i][0] = dp[i-1][0] +..

jinho-study.tistory.com

백준 알고리즘 2156번 포도주 시식(python)

기본적인 다이나믹 프로그래밍 문제이다. 현재 포도주를 마시지 않는 경우, 앞에 포도주를 마시고 현재 포도주를 마시는 경우, 앞에 포도주를 마시지 않고 현재 포도주를 마시는 경우로 총 세

jinho-study.tistory.com

백준 알고리즘 14697번 방 배정하기(python)

간단한 브루트포스 알고리즘 or 다이나믹 프로그래밍 문제이다. 브루트포스 알고리즘 풀이 a, b, c, n = map(int, input().split()) res = 0 for i in range(0, n+1, a): for j in range(0, n-i+1, b): for k in r..

jinho-study.tistory.com

백준 알고리즘 11057번 오르막 수(python)

기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(10): dp[1][i] = 1 for i in range(2, N+1): for j in range(10): for k in range(j+1): dp[i][j] +..

jinho-study.tistory.com

백준 알고리즘 9465번 스티커(python)

기본적인 다이나믹 프로그래밍 문제이다. 뒤쪽 대각선 방향으로 첫 번째, 두 번째 위치의 값 중 큰 걸 선택하면 된다. dp[0][j] += max(dp[1][j-1], dp[1][j-2]) dp[1][j] += max(dp[0][j-1], dp[0][j-2]) for..

jinho-study.tistory.com

백준 알고리즘 11055번 가장 큰 증가 부분 수열(python)

기본적인 다이나믹 프로그래밍 문제이다. 자기 앞에 자기보다 작은 수가 없는 경우도 있는데, 이 부분만 주의하면 쉽게 풀 수 있다. from copy import deepcopy N = int(input()) li = list(map(int, input().spli..

jinho-study.tistory.com

백준 알고리즘 2491번 수열(python)

기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) li = list(map(int, input().split())) dp1, dp2 = [1]*N, [1]*N for i in range(1, N): if li[i] <= li[i-1]: dp1[i] = max(dp1[i], dp1[i-1]+1) if li..

jinho-study.tistory.com

백준 알고리즘 1965번 상자넣기(python)

기본적인 다이나믹 프로그래밍 문제이다. n = int(input()) li = list(map(int, input().split())) dp = [1]*n for i in range(1, n): for j in range(i): if li[i] > li[j]: dp[i] = max(dp[i], dp[j]+1) print(m..

jinho-study.tistory.com

백준 알고리즘 4097번 수익(python)

기본적인 다이나믹 프로그래밍 문제이다. import sys input = sys.stdin.readline while 1: N = int(input()) if N == 0: break li = [int(input()) for _ in range(N)] for i in range(1, N): li[i] = max(li[i],..

jinho-study.tistory.com

백준 알고리즘 11060번 점프 점프(python)

기본적인 다이나믹 프로그래밍 문제이다. N = int(input()) li = list(map(int, input().split())) dp = [N+1]*N dp[0] = 0 for i in range(N): for j in range(1, li[i]+1): if i+j >= N: break dp[i+j] = min(dp..

jinho-study.tistory.com

백준 알고리즘 14430번 자원 캐기(python)

기본적인 다이나믹 프로그래밍 문제이다. 1차원 DP처럼 똑같이 해주면 된다. N, M = map(int, input().split()) li = [list(map(int, input().split())) for _ in range(N)] dp = [[0]*M for _ in range(N)] dp[0]..

jinho-study.tistory.com