Dev On The Coffee Dev On The Coffee

# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n, k = map(int, input().split()) items = [(0, 0)] # 물품 정보 입력 받기 for i in range(n): w, v = map(int, input().split()) items.append((w, v)) # 2차원 DP 테이블 생성 및 초기화 dp = [[0] * (k + 1) for _ in range(n + 1)] # 냅색 알고리즘 수행 for i in range(1, n + 1): # 물품 중 하나를 선택 w = items[i][0] v = items[i][1] # 1 ~ k까지의 무게에 대해 다이나믹 프로그래밍 진행 for j in range(1, k + 1): # 선택한 물품의 무게가 가방 허용 무게를 넘..

# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n = int(input()) nums = [-1001] # 인덱스를 맞추기 위해 가장 작은 수를 하나 삽입 nums = nums + list(map(int, input().split())) # 점화식을 기록하는 테이블을 만들고 초기화 n_sum = [-1001] * 100001 n_sum[1] = nums[1] # 왼쪽부터 차례로 합을 더해나가면서 새로운 수와 비교 for i in range(2, n + 1): n_sum[i] = max(n_sum[i - 1] + nums[i], nums[i]) # 결과 출력 print(max(n_sum)) 생각해볼 점 정석적인 DP 테이블만 생각했는데, 약간 변형하여 점화식을 기록해나가는 방법도 있음을 알았다. 생각을..

# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 str1 = input() str2 = input() dp = [[0] * 1001 for _ in range(1001)] # 최장 공통 부분 수열(LCS) 찾기 for i in range(1, len(str1) + 1): for j in range(1, len(str2) + 1): if str1[i - 1] == str2[j - 1]: # 가장 최근에 추가된 글자가 서로 같을 때 dp[i][j] = dp[i - 1][j - 1] + 1 else: # 추가된 글자가 서로 다를 때 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 결과 출력 print(dp[len(str1)][len(str2)]) 생각해볼 점 아직도 완전히 이..

# 문제 내 풀이 n = int(input()) # 전깃줄의 위치 정보 입력 받음 lines = [] for _ in range(n): a, b = map(int, input().split()) lines.append((a, b)) # A의 위치를 기준으로 전깃줄 위치 정보를 오름차순 정렬 lines.sort(key=lambda x: x[0]) # DP 테이블 생성 및 초기화 dp = [1] * n # B의 수열에서 가장 긴 증가하는 부분 수열(LIS) 찾기 for i in range(1, n): for j in range(0, i): if lines[i][1] > lines[j][1]: dp[i] = max(dp[i], dp[j] + 1) # 없애야 하는 전깃줄의 최소 개수 구하기 print(n - m..

# 문제 내 풀이 n = int(input()) nums = list(map(int, input().split())) # 수열 입력 받기 # 가장 긴 증가하는 부분 수열과 감소하는 부분 수열 각각을 위한 DP 테이블 생성 및 초기화 dp_asc = [1] * 1000 dp_desc = [1] * 1000 # 가장 긴 증가하는 부분 수열 (LIS) 알고리즘 수행 for i in range(1, n): for j in range(0, i): if nums[i] > nums[j]: dp_asc[i] = max(dp_asc[i], dp_asc[j] + 1) # 가장 긴 감소하는 부분 수열 알고리즘 수행 for i in range(n - 2, -1, -1): for j in range(n - 1, i, -1): ..

# 문제 내 풀이 # 내 풀이 n = int(input()) nums = list(map(int, input().split())) # 수열 입력 받기 # DP 테이블 생성 및 초기화 dp = [1] * 1000 # 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행 for i in range(1, n): for j in range(0, i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) # 결과 출력 print(max(dp))

# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n = int(input()) wine = [0] # 인덱스를 맞추기 위해 0 추가 # 와인 정보 입력 받기 for _ in range(n): wine.append(int(input())) # DP 테이블 생성 및 초기화 dp = [0] * 10001 dp[1] = wine[1] if n > 1: dp[2] = wine[1] + wine[2] for i in range(3, n + 1): # 3가지 경우를 고려 # 1. i 번째 와인을 마시지 않는 경우 # 2. i 번째 외인을 마시는 경우 # - 2-1. i - 1 번째 와인을 마시는 경우 # - 2-2. i - 1 번째 와인을 마시지 않는 경우 dp[i] = max(dp[i - 1], dp[i - 3]..

# 문제 내 풀이 # 내 풀이 n = int(input()) # 자리수마다 가장 뒤에 오는 숫자 0 ~ 9를 고려하는 DP 테이블 생성 dp = [[0] * 10 for _ in range(101)] # DP 테이블 초기화 for i in range(1, 10): dp[1][i] = 1 # 바텀업 다이나믹 프로그래밍 수행 for i in range(2, 101): # 0과 9에 대해 점화식 수행 dp[i][0] = dp[i - 1][1] dp[i][9] = dp[i - 1][8] # 1 ~ 8까지의 점화식 수행 for j in range(1, 9): dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] # 결과 출력 print(sum(dp[n]) % int(1e9))