문제 링크 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이 N, M이 각각 10만까지로 만약 범위를 입력받을 때마다 해당 구간에 대해 더하는 연산을 통해 답을 도출한다면 O(NM)의 시간복잡도로 시간초과가 나게됩니다. 매번 합을 도출하는 것이 아니라, 처음에 입력받은 리스트에 대해 누적합을 미리 저장해놓은 후, 만약 i부터 j 인덱스까지의 범위를 구하고 싶을 경우 [ j까지의 누적합 - (i - 1)까지의 누적..
DP
문제 링크 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 문제 문제 풀이 n = int(input()) array = list(map(int, input().split())) dp = [1]*n for i in range(n): for j in range(i): if array[i] > array[j]: dp[i] = max(dp[i], dp[j] + 1) prin..
문제 링크 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 문제 풀이 문제에서 주어진 예제만으로 점화식이 쉽게 구해진 문제였다. P[1], P[2], P[3]까지는 모두 1의 값을 가지고 n이 4부터 100까지의 값일 경우 P[n] = p[n - 3] + p[n - 2] 의 점화식을 가진다. 즉, 수열에서 2개 전, 3개 전 숫자끼리 더한 값이 현재 값이다. p = [0 for i in range(101)] p[1] = 1 p[2] = 1 p[..
문제 링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 문제 풀이 i가 현재 숫자, j가 i보다 작은 제곱수들일 때, dp[i - j] 중 가장 최소항의 개수가 작은 것을 찾아낸다. 이 값에 1을 더해주면 i의 최소항의 개수가 나타난다. (1을 더해주는 이유는 제곱수에 대한 항의 수를 추가하기 위해서이다.) 점화식 => dp[i] = min(dp[i - j]) + 1 n = int(input())..
문제 링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 문제 풀이 전형적인 DP 방식으로 풀리는 문제이다. 주의해야 할 점은 현재 계단(i), 바로 아래 계단을 오를 경우 두 계단을 연속으로 올랐기 때문에 i - 3까지의 최댓값에 두 계단의 값을 더해야 한다는 점이다! n = int(input()) array = [0] * 300 for i in range(n): array[i] = int(input()) dp = [0] * 300 dp[0] = ..
문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 문제 풀이 포도주가 한 개, 두 개 주어졌을 경우는 별다른 계산 필요없이 첫 번째를 선택하는 경우, 첫 번째 + 두 번째를 선택하는 경우가 최대이다. 세 개 주어졌을 경우에는 (1번 + 3번), (2번 + 3번), (1번 + 2번 [두 개 주어졌을 때의 최댓값) 중 최대의 값을 선택하게 된다. 4개부터 n개의 포도주가 주어졌을 때를 보면, 1) n번째 선택 + (n - 1)번째 선택..
문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 설명 문제 풀이 0 1 2 3 4 0 50 10 100 20 40 1 30 50 70 10 60 이 문제는 패턴이 잘 눈에 띄지 않아서 어려웠는데, 결과적으로 굉장히 간단한 패턴을 찾을 수 있다. 예를 들어, dp[0][2]를 선택하고 싶을 경우 앞에서는 dp[1][0] 혹은 dp[1][1]을 선택해야 하는데 둘 중 큰 것을 선택해야만 한다. dp[1][2]를 선택하고 ..
문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 문제 풀이 Dynamic Programming 문제이다. dp 테이블에 모든 원소를 0으로 초기화시켜준 후 하나씩 반복하여 계산을 하는 것이다. DP는 처음에는 이해가 잘 안되는데 생각해보면 간단하다. 예를 들어 4에 대한 연산의 결과를 생각해보자. 4는 4 -> 2 -> 1 의 연산을 하게된다. 그런데 이걸 하나씩 매번 해줄 필요가 없다. 2에 대한 연산의 횟수(DP(2))에 2를 도출해낸 연산(나누기 2) 한 번(+1)을 카운트해주면 DP[4] = DP[2] + 1이 된다. 이와 같은 ..
