[백준] 17626번: Four Squares [C++]
알고리즘 분류: 다이나믹 프로그래밍, 브루트포스 알고리즘 문제 링크: https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 【 풀이 】 DP 문제이다. 즉 규칙을 먼저 찾는 것이 중요한 문제. n의 제곱수들의 최소 개수를 저장한 배열을 dp라고 가정하면, dp[n]은 항상 최적의 해가 된다고 볼 수 있다. 그리고 dp[제곱수]는 항상 그 값이 1이다. dp[1] =1 dp[2] = dp[1] + dp[1] dp[3..
[백준] 11727번: 2*n 타일링 2 [C++]
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 【 풀이 】 역시 다른 DP문제와 마찬가지로, 경우의 수를 계산하면서 규칙을 찾는 것이 중요하다. 2*n 직사각형을 채우는 방법의 수를 저장한 배열을 N이라고 했을 때, N[4] 까지의 값들은 다음과 같다. 1 2 3 4 1 3 5 11 여기서, N[n] = N[n-2]*2 + N[n-1] 이라는 점화식을 도출할 수 있다. 즉 이에 따라 12까지의 값을 나열하면 다음과 같다. 3..
[백준] 11659번: 구간 합 구하기 4 [C++]
알고리즘 분류: 누적 합 문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 【 풀이 】 1~4: (1~4) 2~5: (1~5) - (1~1) 3~6: (1~6) - (1~2) 즉 1~1, 1~2, 1~3, 1~4... 1~end까지의 구간합들을 sum이라는 배열에 따로 저장한다. 그리고 sum[end] - sum[start-1] 을 출력해 주면 끝. 만약 다음에 입력받는 end 변수가 전의 변수보다 더 크다면 ..
[백준] 11726번: 2*n 타일링 [C++]
알고리즘 분류: 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 【 풀이 】 DP 문제이다. 다른 문제들과 마찬가지로 처음부터 경우의 수를 따져가며 규칙성을 찾는 것이 중요하다. 결론적으로는 이 문제는 피보나치수열의 형태를 보인다. N[1] = 1 N[2] = 2 N[3] = 3 N[4] = 5 N[5] = 8, N[6] = 13, N[7] = 21, N[8] = 34, N[9] = 55 즉 N[n] = N[n-2] + N[n-1]...
[백준] 9461번: 파도반 수열 [C++]
알고리즘 분류: 수학, 다이나믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 【 풀이 】 동적계획법으로 해결 가능한 문제이다. 다른 DP 문제들과 마찬가지로 규칙을 찾아 점화식을 도출해 내는 것이 중요하다. 역시 규칙을 찾을 때까지 나열해보고 분석하면 된다. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12 P[1] = 1 P[2] = 1 P[3] = 1 P[4] = P[1] + P[2] = 2 P[5] = P[2..
[백준] 9375번: 패션왕 신해빈 [C++]
알고리즘 분류: 수학, 자료 구조, 조합론, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 【 풀이 】 조합에 대한 수학적 사고력과 이를 해시맵으로 해결하는 능력을 묻는 문제이다. 조합(Combination)에 대해서 깊게 생각해 봤지만, 간단한 아이디어 하나로 풀 수 있는 문제였다. 같은 종류의 의상을 2개 이상..
