https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net ✏️ 문제 🔐 문제 해결 해당 문제는 2xN 스티커가 주어졌을 때, 스티커를 골라 가장 높은 점수의 합을 구하는 문제입니다. 이때 고른 스티커의 좌,우,상,하 스티커는 선택할 수 없게 됩니다. 원래 이 문제는 가로로 arr[0][0] -> arr[0][1] ... -> arr[1][N] 이런 식으로 진행하면서 계산하려 했더니 실패하여서 세로 (arr[0][1] -> arr[1][1] -..
https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net ✏️ 문제 해당 문제는 백준 14501번 (DFS) - 퇴사 문제와 같지만, 시간 복잡도가 O(N) 으로 해결을 해야 통과할 수 있는 문제입니다. 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 🔐 문제 해결 이번에는 DP로 문제를 풀어야합니다. 차근차근 함께 살펴보겠습니다. 1. 테이블 정의 먼저 dp[i]를..
10844번: 쉬운 계단 수 (acmicpc.net) 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 1. 테이블 정의 dp[i][j]는 길이가 i이고, j로 시작하는 수들 중 계단 수의 개수를 뜻합니다. 설명이 부족한 듯 해보여 아래의 표 형태로 표현해보았습니다. 0으로 시작하는 수는 없다고 조건에 나와있지만, 점화식을 세우기 위해서는 0으로 시작하는 계단 수도 필요합니다. dp[i][j]에는 위 표에서 정의한 대로 개수가 들어갈 것입니다. 여기서 중요한 포인트는 dp[1][0] = 0이라고 해서 개수가 0이 아닙니다! 1개로 체크해줘야 아래 점화식이 성립합니다. 2. 점화식 세우기 위 표를 참고하..
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ✏️ 문제 🔐 문제 해결 문제를 이해하지 못해서 헤맸던 문제이다.. 아래 설명과 함께 풀이를 해보겠습니다. 1. 테이블 정의 1차원 배열 dp[i]는 i 번째 수까지의 가장 긴 증가하는 수열의 길이를 뜻합니다. 아직 잘 이해가 안되시는 분들을 위해 아래 코드로 설명해보겠습니다. 10 20 30 20 30 dp[0] = ..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ✏️ 문제 🔐 문제 해결 나란히 놓여있는 포도주를 마셔서 가장 많이 마신 양을 출력하면 되는 문제입니다. 이 문제를 보면서 계단오르기 문제와 유사하여 해당 문제 풀이 방식대로 푼다면 틀리게 됩니다. 이번 문제에는 포도주를 마시지 않는 경우도 있을 수 있으므로, 해당 경우도 잘 생각해줘야 합니다. 문제에서 주어진 예제를 살펴보면, 가장 많이 마실 수 있는 방법은 아래와 같을 것입니다. 첫 번째, 두 ..
https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net ✏️ 문제 🔐 문제 해결 1. 테이블 정의 dp[i][j]의 i값은 i 번째 피보나치 수를 의미하고, j(=0, 1)는 해당 피보나치수의 0의 출력 횟수와 1의 출력 횟수를 나타냅니다. dp[i][0] = i 번째 피보나치 수의 0 출력 횟수 dp[i][1] = i 번째 피보나치 수의 1 출력 횟수 2. 점화식 세우기 3 번째 피보나치 수에 대해서 생각해보겠습니다. fibonacci(3)은 fibonacci(2) + fibonacci(1) 입니다. fibonacci(2)는 fibonacci(0..
