문제풀이/백준(Boj) 문제풀이 188

[백준][동적 계획법1] 2565 . 전깃줄 (파이썬/Python)

import sys input = sys.stdin.readline n = int(input()) lst = [] lst_2 = [] dp = [0]*n for _ in range(n): lst.append(list(map(int,input().split()))) # A순으로 정렬 lst.sort(key = lambda x:x[0]) #A순으로 정렬한 리스트목록에서 B만 리스트2에 담아 줌 for i in range(n): lst_2.append(lst[i][1]) for i in range(n): for j in range(i): if lst_2[i] > lst_2[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] += 1 #입력받은 n에서 긴수열의 값을 빼준 것이 교차하는 전..

[백준][동적 계획법1] 11053. 가장 긴 증가하는 부분 수열LIS(파이썬/Python)

#11053 import sys input = sys.stdin.readline n = int(input()) a_list = list(map(int,input().split())) #DP를 위한 1차원 DP테이블 초기화 dp = [1]*n #가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행. for i in range(1,n): for j in range(0,i): if a_list[j] < a_list[i]: dp[i] = max(dp[i],dp[j] +1 )# 1 print(max(dp)) # 1 DP의 경우 중복된 함수를 불러서 쓰는 것 대신 쓴 값을 저장해서 쓰는 방식이기 때문에 이를 위해서 이미 쓴 값인지를 확인

[백준][동적 계획법1] 2156 . 포도주 시식(파이썬/Python)

#2156 import sys input = sys.stdin.readline n = int(input()) a = [0]*10000 for i in range(n): a[i] = int(input()) dp = [0]*10000 dp[0] = a[0] dp[1] = a[0]+a[1] dp[2] = max(a[0]+a[2],a[1]+a[2],dp[1]) #dp[1] == a[0]+a[1] for i in range(3,n): dp[i] = max(a[i]+dp[i-2], a[i]+a[i-1]+dp[i-3],dp[i-1]) print(max(dp)) #2156 import sys input = sys.stdin.readline n = int(input()) a = [0 for i in range(10000..

[백준][동적 계획법1] 1463 . 1로 만들기(파이썬/Python)

import sys input = sys.stdin.readline n = int(input()) #1부터 사용하는 것으로 쓰기 위함 dp = [0] * (n+1) for i in range(2,n+1): dp[i] = dp[i-1]+1 if i % 3 == 0: dp[i] = min(dp[i],dp[i//3]+1) if i % 2 == 0: dp[i] = min(dp[i],dp[i//2]+1) print(dp[n]) # 메모이제이션(memoization) 기법을 사용 # 한 번 사용하는 것을 중복해서 사용하지 않고 저장한 것을 이용해서 사용하는 기법. # 그리디와 다른 점은 최적의 해를 찾기 위해서 냅다 3을 나눠서 시작하는 것과 다르게 최적의 해를 구하려면 모든 경우를 써봐야 안다는 점에서 DP를 사..

[백준][동적 계획법1] 2579. 계단 오르기(파이썬/Python)

import sys input = sys.stdin.readline n = int(input()) s = [0 for i in range(301)] dp = [0 for i in range(301)] for i in range(n): s[i] = int(input()) dp[0] = s[0] dp[1] = s[0]+s[1] dp[2] = max(s[1]+s[2],s[0]+s[2]) #마지막의 경우엔 꼭 밟아주어야 하기 때문에 바로 직전의 것을 밟은 것과 안 밟은 것 for i in range(3,n): dp[i] = max(dp[i-3]+s[i-1]+s[i],dp[i-2]+s[i]) print(dp[n-1]) # dp[2]의 경우엔 s[0]을 건너뛰고 s[1]에서 s[2]를 밟은 경우와 s[0]에서 s[..

[백준][동적 계획법1] 1932. 정수 삼각형(파이썬/Python)

import sys input = sys.stdin.readline n = int(input()) tri = [] for _ in range(n): tri.append(list(map(int,input().split()))) for i in range(1,n): for j in range(len(tri[i])): # 처음 각 라인의 처음과 끝 -> 바로 위의 숫자를 더해준다 if j == 0: tri[i][j] = tri[i][j]+tri[i-1][j] # 끝 elif j == len(tri[i])-1: tri[i][j] = tri[i][j]+tri[i-1][j-1] #나머지는 왼쪽 대각선, 오른쪽 대각선 중 최댓값을 더해나가 계속 누적시켜주면 된다. else: tri[i][j] =max(tri[i-1]..

[백준][백트래킹] 14888. 연산자 끼워넣기(파이썬/Python)

import sys input = sys.stdin.readline def dfs(cnt, result, p, m, mul, div): global max_result global min_result if cnt == n: max_result = max(max_result, result) min_result = min(min_result, result) return if p: dfs(cnt + 1, result + a[cnt], p - 1, m, mul, div) if m: dfs(cnt + 1, result - a[cnt], p, m - 1, mul, div) if mul: dfs(cnt + 1, result * a[cnt], p, m, mul - 1, div) if div: dfs(cnt + 1, -..

[백준][동적 계획법1] 9461. 파도반 수열 (파이썬/Python)

[1 1 1 2 2 3 4 5 7 9 12 16 21 29 38 50 ...] [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...] a = [0 for i in range(101)] a[1]= 1 a[2]= 1 a[3]= 1 for i in range(1,98): a[i + 3] = a[i] + a[i + 1] t = int(input()) for i in range(t): n = int(input()) print(a[n]) #a[i+3]번째가 a[i]+a[i+1]임 #a[3] = a[1] + a[2] ⁛ 2 = 1+1 a = [0 for i in range(101)] a[1]= 1 a[2]= 1 a[3]= 1 for i in range(0,98): a[i + 3] = a[i]..