알고리즘

가장 긴 바이토닉 부분 수열 [백준 11054] - python

import sys input = sys.stdin.readline def BOJ11054() : n = int(input()) l = list(map(int, input().split())) dp_up = [1 for _ in range(n)] dp_down = [1 for _ in range(n)] for i in range(n) : for j in range(i) : if l[i] > l[j] : dp_up[i] = max(dp_up[i], dp_up[j]+1) for i in range(n-1, -1, -1): for j in range(n-1, i-1, -1): if l[i] > l[j]: dp_down[i] = max(dp_down[i], dp_down[j]+1) dp = [] for up, ..

팰린드롬? [백준 10942] - python

import sys input = sys.stdin.readline def BOJ10942() : n = int(input()) l = list(map(int, input().split())) m = int(input()) dp = [[0 for _ in range(n)] for _ in range(n)] for diff in range(n) : for start in range(n - diff) : end = start + diff if start == end : dp[start][end] = 1 continue if start + 1 == end : if l[start] == l[end] : dp[start][end] = 1 else : dp[start][end] = 0 continue if l[st..

내리막 길[백준 1520] - python

import sys input = sys.stdin.readline def BOJ1520() : global M, N global l directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] def get_load(dp, curr_x, curr_y): if curr_x == M - 1 and curr_y == N - 1 : return 1 if dp[curr_x][curr_y] != -1 : return dp[curr_x][curr_y] dp[curr_x][curr_y] = 0 for dir_x, dir_y in directions : next_x = curr_x + dir_x next_y = curr_y + dir_y if 0

가장 긴 감소하는 부분 수열 [백준 11722] - python

import sys input = sys.stdin.readline def BOJ11722() : n = int(input()) l = list(map(int, input().split())) dp = [1 for _ in range(n)] for i in range(n) : for j in range(i) : if l[i] < l[j] : dp[i] = max(dp[i], dp[j] + 1) print(max(dp)) BOJ11722() 접근 방법 : 1. 가장 긴 증가하는 부분 수열의 번외편이다. 이전의 최대 길이를 이용해야 하므로 dp를 이용해 주었다. 2. 현재 비굣값에서 이전 인덱스까지의 값을 모두 탐색해 주면서 자신보다 큰 값이 있으면 그 값에서의 길이 + 1과 현재 최대 길이를 비교해 준다...

제곱수의 합 [백준 1699] - python

import sys input = sys.stdin.readline def BOJ1699() : n = int(input()) dp = [1e9 for _ in range(100001)] dp[0] = 0 dp[1] = 1 dp[2] = 2 dp[3] = 3 for i in range(4, n+1) : if (i ** (0.5)) % 1 == 0 : dp[i] = 1 else : number = int(i ** (0.5) // 1) for j in range(1, number+1) : if i % (j ** 2) == 0 : dp[i] = min(dp[i], i // (j ** 2)) else : head, _ = divmod(i, j ** 2) dp[i] = min(dp[i], head + dp[i -..

오르막 수[백준 11057] - python

import sys input = sys.stdin.readline mod_num = 10_007 def BOJ11057() : n = int(input()) dp = [[0 for _ in range(10)] for _ in range(n+1)] dp[1] = [1 for _ in range(10)] for i in range(2, n+1) : for j in range(10) : dp[i][j] = sum(dp[i-1][:j+1]) % mod_num print(sum(dp[n]) % mod_num) BOJ11057() 접근 방법 : 1. dp는 끝자리가 i 인 숫자의 개수를 나타내는 배열이다. 2. 끝자리 i를 만들수 있는 숫자는 dp[n-1]의 끝자리 i 까지의 숫자들의 합이다. 1자리 수 만들수 ..

퇴사 [백준 14501] - python

import sys input = sys.stdin.readline def BOJ14501() : n = int(input()) work = [] for _ in range(n) : work.append(list(map(int, input().split()))) dp = [0 for _ in range(n+1)] day, cost = work[0] for i in range(n-1, -1, -1) : day, cost = work[i] complete_day = i + day if complete_day

2xn 타일링 2 [백준 11727] - python

import sys input = sys.stdin.readline mod_num = 10_007 def BOJ11727() : n = int(input()) dp = [0 for _ in range(1001)] dp[1] = 1 dp[2] = 3 for i in range(3, 1001) : dp[i] = ((dp[i-2] * 2) % mod_num + (dp[i-1]) % mod_num) % mod_num print(dp[n]) BOJ11727() 접근 방법 1. 3번째 인덱스부터 도형을 그리려면 n-1 번째에서는 [2x1] 타일밖에 이용을 할 수가 없다. n-2 번째에서는 [1x2] 두개, [2x2] 하나를 이용하는 방법 두개씩 가능하다 이를 점화식으로 나타내면 dp[n] = dp[n-2] * 2 ..

이친수 [백준 2193] - python

import sys input = sys.stdin.readline def BOJ2193() : n = int(input()) dp = [[0 ,0] for _ in range(91)] dp[1] = [0, 1] dp[2] = [1, 0] for i in range(3, 91) : dp[i] = [sum(dp[i-1]), dp[i-1][0]] print(sum(dp[n])) BOJ2193() 접근 방법 1. 1은 연속될 수가 없다. 숫자를 이어 붙일수 있는 건 이전의 숫자에 영향을 받게되므로 dp를 이용하게 되었다. 2. dp 배열은 끝자리가 0, 1로 끝나는 수의 개수를 의미한다. 3. n 자리수에서 끝자리가 0이 되는 경우는 n-1 자리수의 합, 끝자리가 0이 되는 경우의 수는 n-1자리수에서 끝이 ..

쉬운 계단 수 [백준 10844] - python

import sys input = sys.stdin.readline mod_num = 1_000_000_000 def BOJ10844() : n = int(input()) dp = [[0 for _ in range(10)] for _ in range(101)] dp[1] = [0] + [1 for _ in range(9)] for i in range(2, 101) : for j in range(10) : if j == 0 : dp[i][j] = dp[i-1][1] % mod_num elif j == 9 : dp[i][j] = dp[i-1][8] % mod_num else : dp[i][j] = (dp[i-1][j-1] % mod_num + dp[i-1][j+1] % mod_num) % mod_num pr..