https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. Logic 부분문제를 나눠보자면 1. 오름차순으로 받는경우 1-1. 이전에 선택한 숫자보다 현재 인덱스의 숫자가 큰경우 > 선택 1-2. 이전에 선택한 숫자보다 현재 인덱스의 숫자가 작은 경우 > 내림차순으로 변경하고 선택 2. 내림차순으로 변경된 경우 2-1. 이전에 선택한 숫자보다 현재 인덱스의 숫자가 작은경우 > 선택 3. 선택안하고 인덱스를 넘기는 경우 2. Code #include using names..
DP
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 1. Logic 해당 문제를 환형으로 보지말고 그냥 직선형으로 봐서 0번째 색깔을 선택하는 경우와 0번째 색깔을 선택하지 않는 경우 2가지로 나눠서 해결했다. 0번째 색깔을 을 선택하는 경우는 1번째 색깔을 절대로 선택 못하기 때문에 인덱스를 2로 올려준 후 함수로 전달한다. 0을 선택하지 않는 경우는 1번 색깔을 선택해도 되고 안해도 되기 때문에 인덱스는 1, cnt는 0 으로 넣어준다 2. Code #include ..
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 1. Logic 0~n-1까지 순회하면서 각 시작 위치보다 큰 숫자만 더해주면서 최댓값을 구해주면 된다. 코드를 보면 이해가 쉬울 것 이다. 2. Code #include using namespace std; int n; vector input; //증가하는 부분수열의 합 int dp[1001][1001]; int solve(int id..
https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 1. Logic 브루트 포스로 풀 수 있지만 각 칸에서의 최솟값은 변하지 않기 때문에 그 값을 저장해 놓고 DP로 풀이할 수 있다. 2. Code #include using namespace std; int n, m; int space[10][10]; int dp[10][10][4]; //0:왼 1:dir 2:오 int solve(int y, int x, int p..
https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. Logic 처음에 이 문제를 딱 보고 위상정렬인줄 알았다. 하지만 위상정렬의 탈을 쓴 DP문제였고 결국 멘토한테 도움을 받았다. 내가 처음에 짠 코드는 동시에 진행하는 작업 중에 가장 시간이 오래 걸리는 작업의 시간이 고려되지 않을 수도 있는 코드였다. 그래서 이 문제는 위상정렬과 코드가 비슷하긴 하지만 DP로 풀이해야 한다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1. Logic 재귀로 들어가서 0이 되면 경우의 수 1을 count해준다. 다만 숫자가 크기 때문에 타입을 long long 으로 해줬다. 2. Code #include #include using namespace std; long long dp[1000001]; long long solve(long long n) { if(n == 0) return 1; else if(n < 0) return 0; long long &ret = dp[n]; if..
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. Logic LIS약간 변형? str1과 str2의 문자가 같으면 이전최대길이에 +1을 해준다! 2. Code #include using namespace std; int dp[4001][4001]; string str1, str2; int solve(int s1, int s2) { if(s1 == str1.size() || s2 == str2.size()) return 0; int..
https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. Logic 먼저 dp테이블의 의미는 dp[i] i개의 돌에서 턴을 잡은 사람의 승패 유무이다. 문제에서 1개, 3개, 4개를 가져갈 수 있다고 했고 항상 상근이가 먼저 시작한다고 했기 때문에 돌 갯수 | 우승자 1개 | 상근이 2개 | 창영이 3개 | 상근이 4개 | 상근이 항상 이렇게 이기고 이후는 이전에 메모이제이션 된 값으로 부분문제가 쪼개지기 때문에 DP로 풀 수 있다. 항상 두 사람이 완벽하게 게임을 한다고 했으며 항상 상근이가 먼저 시작하기 때문에 한번이라도 상근이가 이기는 경우가 생기면 해당 n개..
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. Logic 이 문제의 부분문제는 총 3가지로 나눌 수 있다. 1. 사자를 배치하지 않는 경우(항상) 2. 사자를 오른쪽에 배치하는 경우(이전에 사자를 왼쪽에 배치했을 때) 3. 사자를 왼쪽에 놓는경우 (이전에 사자를 오른쪽에 배치했을때) 이렇게 3가지 경우를 끊어서 해결해주면 된다. 아래 코드를 보면 이해가 될 것이다. 2. Code #include #include using namespace std; int n; int dp[100001][3]; int solve(int idx, int prev) { if(idx == n)..
https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. Logic 부분문제를 3가지로 나눌 수 있다. 포도주를 안마시는 경우 포도주를 1잔 연속해서 마시느 경우 포도주를 2잔 연속해서 마시는 경우 그래서 DP테이블을 정할 때 DP[현재 인덱스][선택 여부] 로 정의했다. 선택 여부 별 의미하는 바는 > 0:이전에 포도주 안마심, 1:이전에 한잔만 마심, 2:이전에 두잔 연속해서 마심 입력으로 받은 첫번째 수에서 선택할지 말지여부를 처리하는 것은, ..
