네발로 코딩하는 포메라니안

1. 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이과정 순서에 대한 순열에서 1)중간에 결과보다 작은 값이되거나 2)비트마스킹으로 불필요한 연산을 가지치기하는 것이 핵심이다. 예를 들어 N = 5일 때, 1~3까지 0~2번째 중에 하나씩 선택했다고 하면, 뒤에는 나머지는 3, 4번째 중에 선택한다. 이때 1~3까지 012, 021, 102, 120, 201, 210 순서가 가능한데, 이들 모두가 남은 것들의 최적값은 같다. 남아..

1. 문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 2. 풀이 과정 소수 구하기는 에라토스테네스의 체를 사용했고, 연속된 수의 합은 dp를 활용했다. 2부터 N까지 보면서, 소수가 보이면 values배열에 더한 값을 저장한다. 예시로 N=15일 때를 생각해보면, i=2 values = [2] i=3 values = [5, 3] i=4 values = [9, 7, 4] i=5 values = [14, 12, 9, 5] i=6 values = [20, 18, 15, 11, 6] => result++; ... 15보다 큰 값은 N(15)가 될 가능성이 없으므로,..

1. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이 과정 재귀 + 2차원 배열 DP문제라고 할 수 있다. 처음엔 순열을 돌려서 전체 탐색을 했는데 경우의 수가 16!으로 결국 시간 초과가 발생했다. 해결 방안이 떠오르지 않아, 질문을 보고 힌트를 얻어 풀 수 있었다. 이 문제의 key point는 2가지다. 1) 루프는 시작점이 어디든, 더해지는 값이 같기 때문에 값의 총합은 같다. => ..

1. 문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2. 풀이과정 채운다 = 빈칸없게! 1) n이 0이나 홀수면, 0을 출력 2) 짝수면 아래의 규칙을 따름 p[n] = (p[n-2]*3) + (p[n-4]*2) + (p[n-6]*2) + ... = (p[n-2]*3) + (p[n-4] + p[n-6] + ... )*2 2칸일 때, 가능한 건 3가지, 4칸일 때만 가능한 건 2가지, 6칸일 때만 가능한 건 2가지, ... , 그 뒤로 모두 2가지씩 있다. 여기서 6칸일 때만 가능하다는 말은 n=2, n=4일 때처럼 6보다 작은 타일에서 블럭을 어떻..

1. 문제 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 풀이 과정 1 => N번째 집을 차례대로 색을 칠한다. 각자 자신의 앞의 집의 색깔만 피하면 된다. 단, 마지막 집은 첫 번째 집의 색깔도 고려해야하기 때문에 처음부터 첫 번째 집의 색에 따라 나눠 계산했다. 첫 번째 집 색에 따라 R[], G[], B[]를 만들어서 값을 업데이트해갔다. 이는 Dynamic Programming을 사용한 풀이 방법이라 ..