답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/2449 문제 풀이 : DP 문제입니다. cache[L][R] : L번째 전구부터 R번째 전구까지 통일 시키는데 색을 바꾼 최소횟수 양쪽 구간의 색을 통일 시킬때 변수를 하나 두시고 양쪽 구간의 시작 색깔이 같다면 바꾸는 비용을 0으로, 다르다면 바꾸는 비용을 1로 계산하여 쌓아가시면 됩니다.

문제 출처 : https://www.acmicpc.net/problem/2342 문제 풀이 : DP문제입니다. cache[idx][l][r] : idx번째 지시사항이고 왼발이 l번째칸 오른발이 r번째 칸에 있을때의 사용된 최소힘 이라고 두고 cache를 쌓으시면 됩니다. 칸별로 이동시 드는 힘은 dir[5][5] 배열을 선언하여 편하게 처리하도록 합시다.

문제 출처 : https://www.acmicpc.net/problem/8902 풀이 : 2차원 DP문제입니다. 두개의 라인이 존재하는데 각라인에서 몇대가 합류했는지를 DP로 쌓으시면 됩니다. 저는 cache[line1][line2]의 형태로 저장했습니다. 문제에서 원하는 결과값은 결국 모든 끝나는 지점에서 모든 시작지점을 뺀 값과 같습니다 따라서 cache를 쌓을때 각 색깔별로 맨처음과 맨끝이 어디있는지를 비교하여 1. 그 색깔에서 맨 처음 나왔을 경우 : 그 위치를 (-) 해줌 2. 그 색깔에서 맨 마지막에 나왔을 경우 : 그 위치를 (+) 해줌 위의 두개지 규칙을 적용하여 풀었습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 출처 : https://www.acmicpc.net/problem/9095 풀이 : DP문제입니다. 1, 2, 3으로 새로운 방법을 만들 수 있는 경우는 i-1인 경우 : + '1' i-2인 경우 : + '2' i-3인 경우 : + '3' 이 세가지 경우 입니다. 따라서, cache[i] = cache[i-1]+cache[i-2]+cache[i-3]대로 쌓으면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include int t,n,cache[11]; int main() { scanf("%d", &t); cache[1] = 1, cache[2] = 2,cache[3] =4; for (int i = 4; i

문제 출처 : https://www.acmicpc.net/problem/11055 풀이 : DP문제 입니다. 가장 큰 값을 가지는 LIS가 아니라 가장 큰 값을 가지는 증가 부분 수열 이라는 점에 주의합시다. 값을 쌓아 가실 때 이전까지 증가 수열 중 현재 값과 증가 수열을 이루면서 가장 큰 값을 갖는 증가수열이 되도록 쌓아가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include int n,arr[1000],cache[1000],max; int main() { scanf("%d", &n); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/16500 풀이 : DP문제입니다. 문자열을 처음부터 끝까지 훑으면서 단어들과 매칭합니다 그리고 단어 목록들로 문자열의 현재 시점까지 완성 시킬 수 있는지 없는지 여부를 word배열에 쌓아가는데, 쌓을 때 현재 검사하고있는 S문자열의 바로 앞 문자까지 완성되있는지 여부를 확인하고 완성되어 있으면 word 배열에 완성 됬다고 쌓아가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include char comp[101]; char carr[101][101]; int n,word[101]; int main() { scanf("%s", comp)..

문제출저 : https://www.acmicpc.net/problem/11052 풀이 : DP문제입니다. 동전문제와 거의 일치합니다. 메모이 제이션을 할 때 현재 cache에 쌓여있는 값과 이 팩을 샀을때의 값을 비교하여 쌓아가면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n,card[1001],cache[1001]; int main() { scanf("%d", &n); for (int i = 1; i

문제 출저 : https://www.acmicpc.net/problem/11727 풀이 : DP문제 입니다. 1x2 타일, 2x1타일, 2x2타일을 이용해 타일링을 합니다 2x1타일은 2x2타일로 만들어서 사용해야 하므로 2x2와 같은 경우에 들어가도록 계산하되, 다른 경우로 여겨주시면 됩니다. N=1일때 1 N=2일때 3 N>=3일때 N-1패턴에서 1x2타일을 붙이는 경우, N-2패턴에서 2x1타일 2개, 2x2타일 1개를 붙이는 경우를 더하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n, cache[1001]; int main() { scanf("%d", &n); cache[1] = 1; cache[2] = 3; for (int i = 3; i

문제 출저 : https://www.acmicpc.net/problem/1904 풀이: DP문제입니다. N=1 일때 1 N=2 일때 1,00 N>=3 일때 [N] = [N - 2] + [N - 1]입니다. N>=3일때 점화식이 저렇게 나오는 이유는 N일때의 타일패턴은 N-1 에서 1타일을 추가한 것, N-2에서 00타일을 추가한 것 뿐이기 때문입니다. 1 2 3 4 5 6 7 8 9 10 11 12 #include int n, cache[1000001]; int main() { scanf("%d", &n); cache[1] = 1; cache[2] = 2; for (int i = 3; i

문제 출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN 풀이 : 완전탐색과 DP를 합쳐놓은 문제입니다. 우선 완전탐색으로 행렬을 찾고 연쇄행렬 최소곱셈 알고리즘을 사용하면 됩니다.(DP) 행렬을 찾는 과정은 제약 사항 중 부분 행렬의 열의 개수는 서로 다르며 행렬의 행의 개수도 서로 다르다는 조건에 따라 [SWEA 1259] 금속 막대 이 문제에서 설명 드린 것과 유사하게 찾을 수 있습니다. N X M 행렬에서 N부분은 check 배열에서 ++, M부분은 check 배열에서 -- 하여 유일한 곱셈 순서를 찾고 연쇄행렬 최소곱셈 알고리즘을 사용합니다. (55 ~ 66라인) ..