[Baekjoon] #2156 - 포도주 시식
PS/백준2022. 8. 2. 13:43[Baekjoon] #2156 - 포도주 시식

입력 6 6 10 13 9 8 1 연속적으로 3잔을 모두 마실 수 없다는 제한이 걸린 문제이다. n번째에 제한을 두는 문제는 i번째를 기준으로 (i - 1), (i - 2), (i - 3).. 번째를 생각봐야한다. n = int(input()) grape = [0] sum = 0 for _ in range(1, n + 1): grape.append(int(input())) dp = [0, grape[1]] if n > 1: # 포도주가 1잔일 수 있음 dp.append(grape[1] + grape[2]) for i in range(3, n+1): dp.append(max(dp[i-1], dp[i-2] + grape[i], dp[i-3] + grape[i] + grape[i-1])) # 차례로 이번 차례..

[Baekjoon] #1912 - 연속합
PS/백준2022. 8. 2. 11:14[Baekjoon] #1912 - 연속합

10 10 -4 3 1 5 6 -35 12 21 -1 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구해야 한다. 여기서 연속된 몇개의 수는 연속적으로 증가하는 수가 아닌 배열의 인접한 수임에 주의하자 !!!! 만약 연속적인 배열의 값이 모두 양수라면 해당 값들을 모두 더해준다. 이때 현재 인덱스의 배열값이 음수라고 해보자 그 음수 값을 더한 누적 합에 다음 인덱스 배열값을 더하면 다음 인덱스 배열에 있던 기존의 값보다 작아질 수 있다. 입력 예시로 생각해보자 10 6 9 10 15 21 -14 12 33 32 21 + (-35)의 값은 -14이다. 해당 값에 + 12를 하면 -2 값이 나온다. -2 값은 기존의 12 값보다 작으므로 걸러지고 기존 값인 12가 남는다. 만약 여기서 다..

[Beakjoon] #11054 - 가장 긴 바이토닉 부분 수열
PS/백준2022. 8. 2. 09:35[Beakjoon] #11054 - 가장 긴 바이토닉 부분 수열

정방향, 역방향 가장 긴 증가하는 수열을 구한뒤 각 dp의 값을 합쳐준다. 이때 -1을 하는 이유는 바이토닉 수열의 변곡점 부분의 dp 값이 2번 카운팅되기 때문이다. N = int(input()) A = list(map(int, input().split())) A.insert(0, 0) dpf = [1] * (N + 1) # 정방향 dpr = [1] * (N + 1) # 역방향 dps = [1] * (N + 1) # 합칠 때 for i in range(1, N + 1): for j in range(1, i): if A[j] < A[i]: dpf[i] = max(dpf[i], dpf[j]+1) for i in range(N, 0, -1): for j in range(N, i, -1): if A[j] < ..

[Beakjoon] #11055 - 가장 큰 증가 부분 수열
PS/백준2022. 8. 1. 22:24[Beakjoon] #11055 - 가장 큰 증가 부분 수열

6번 정도 실패하고 반례 테스트케이스 보고 해결한 문제 ㅠ_ㅠ 처음 생각한 코드는 다음과 같다. n = int(input()) a = list(map(int, input().split())) a.insert(0, 0) dp = [0] * (n + 1) dp[1] = a[1] for i in range(1, n + 1): for j in range(1, i): if a[j] < a[i]: dp[i] = max(dp[i], a[i] + dp[j]) # print(dp) print(max(dp)) 해당 코드로 문제에 주어진 입력 예제를 넣었을 때는 정답이 출력되지만 채점시 틀렸다고 떴다. 반례 6 10 20 10 30 20 50 다음과 같이 입력이 주어졌을 때 내가 원했던 dp는 [10, 30, 10, 60,..

[Beakjoon] #9465 - 스티커
PS/백준2022. 8. 1. 15:56[Beakjoon] #9465 - 스티커

풀 때도 이해가 안갔지만 풀이를 보고도 애매한 문제 .. ㅎㅎ 우선 스티커의 위치와 값을 배열로 만들면 다음과 같다. index 0 1 2 3 4 0 50 10 100 20 40 1 30 50 70 10 60 이제 조건을 생각해보자 어떤 자리를 하나 선택하면 그 자리의 상, 하, 좌, 우는 더 이상 쓸 수 없는 스티커가 된다. 예를 들어 50을 선택한다고 하면 양옆의 그 양옆인 10, 30은 더 이상 사용할 수 없게된다. index 0 1 2 3 4 0 50 10 + 30 = 40 max(100, 30) + 100 = 200 max(120, 100) + 20 = 140 max(210, 120) + 40 = 250 1 30 50 + 50 = 100 max(40, 50) + 70 = 120 max(200, ..

[DP] 1로 만들기
PS/이코테2022. 2. 22. 22:59[DP] 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. a. X가 5로 나누어떨어지면, 5로 나눈다. b. X가 3으로 나누어떨어지면, 3으로 나눈다. c. X가 2로 나누어떨어지면, 2로 나눈다. d. X에서 1을 뺀다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 1. 26 - 1 = 25 (4) 2. 25 / 5 = 5 (1) 3. 5 / 5 = 1 (1) 입력 조건 첫째 줄에 정수 X가 주어진다. (1 26 -> 25 -> 5 -> 1 28 -> 14 -> 7 -> 6 -> 2 -> 1 두가지 방법은 연산의 횟수가 같다. 즉..

image