[C++] 백준 11053번 : 가장 긴 증가하는 부분 수열 (S2)
#문제 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #풀이 & 학습한 내용 시간복잡도를 O(N)으로 구현하려 시도했지만 실패하고 O(N^2)로 구현했다. dp배열에 그 위치를 수열의 마지막으로 갖는 최대 증가하는 부분 수열의 길이를 저장했다. j가 1부터 i까지 움직이며 p[j]dp[i] 조건이 만족되면 갱신되도록 for문을 구성했다. 그리고 문제에서 구하는 최댓값은 dp배열의..
[C++] 백준 15990번 : 1, 2, 3 더하기 5 (S3)
#문제 www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 중복이 안 되게 해야 하므로 마지막이 어떤 수인지에 대해 구분을 하여 경우의 수를 저장해주어야 한다. 2차원 배열을 선언하여 마지막에 더해지는 수 1, 2, 3에 대해 그 인덱스에 맞는 곳에 경우의 수를 저장한다. 인덱스를 0부터 해도 되지만 마침 마지막에 더해지는 수가 1 ,2, 3이므로 편하게 인덱스 또한 1,2,3일 때에 해당되도록 해서 헷갈리는 일이 없게 했다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13..
[C++] 백준 15988번 : 1, 2, 3 더하기 3 (S2)
#문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 int 범위의 최대는 2,147,483,647이다. 대략 2,000,000,000으로 기억해두자. 문제에서 dp배열을 int로 선언하면, dp[i - 1] + dp[i - 2] + dp[i - 3]을 계산할 때, int범위의 최댓값을 벗어날 수 있다. 따라서 dp배열을 long long으로 선언해야 한다. 모듈로 연산의 성질인 (A + B)%C = (A%C + B%C)%C도 기억해두자. 이때, (A%C + B)%C도 가능하다는 점도..
[C++] 백준 9095번 : 1, 2, 3 더하기 (S3)
#문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 마지막에 올 수 있는 수는 1,2,3 중 하나이다. 그리고 마지막 수를 빼면 같은 문제로 문제의 크기만 n-1, n-2, n-3이 되므로 dp를 이용한다. 이때 dp배열의 초깃값으로 dp[1]=1, dp[2]=2, dp[3]=4를 넣어주고 반복문으로 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]을 통해 dp[10]까지 계산한다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #inclu..