Henzee's Archive

문제 링크     문제 분석 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제이다.  문제 풀이 dp[n] = 2×n 직사각형을 3가지 타일로 채우는 방법의 수 라고 정의하자.  아래 그림을 보면,dp[1] = 1dp[2] = 3 이다. dp[n] 의 경우의 수를 구해주기 위해서dp[n-1] 의 경우의 수와 dp[n-2] 의 경우의 수를 보자. dp[n-1] 은 끝에 2×1 타일을 놓는 경우의 수를 구해주면 된다. dp[n-2] 는 끝에 1×2 타일 두개를 놓는 경우의 수와 2×2 타일을 놓는 경우의 수 두 가지를 모두 구해줘야 한다. 따라서, dp[n] = dp[n-1] + dp[n-2] * 2 와 같다.추가로 위의 값에 10,007 로 나눈 나머지를 저장하면 된다.  ..

문제 링크     문제 분석합의 최대를 구하기 위해서 DP를 활용해서 풀어야하는 문제이다.dp[i][j]를 (i, j) 위치까지 내려올 때의 최댓값이라고 정의하자. 입력이 아래와 같이 주어졌을 때,(i, j)0123407    138   2810  32744 445265 dp 배열을 아래와 같이 채울 수 있다.(i, j)0123407    11015   2181615  320252019 42430272624 위 결과를 보고 점화식을 유도할 수 있다.j == 0 (왼쪽 끝)인 경우 dp[i][0] = dp[i - 1][0] + triangle[i][0]j == i (오른쪽 끝)인 경우 dp[i][i] = dp[i - 1][i - 1] + triangle[i][i] 중간 값인 경우 dp[i][j] = max..

문제 링크     문제 분석N개의 집을 양 옆에 있는 집의 색이 겹치지 않게 빨강, 초록, 파랑 3가지 색을 칠할 때 집을 칠하는 최소 비용을 구하는 문제이다.  문제 풀이 house[i][0]은 i번째 집을 빨강색으로 칠하는 최소 비용house[i][1]은 i번째 집을 초록색으로 칠하는 최소 비용house[i][2]는 i번째 집을 파랑색으로 칠하는 최소 비용 만약, i번째 집을 빨강색으로 칠하려면 i - 1번째 집들 중 초록, 파랑 중에 최소 비용에다가 i번째 집을 빨강색으로 칠하는 비용을 더해주면 된다.   최종 제출 코드 #include #include #include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin..

문제 링크       문제 분석정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.n은 1보다 크고 11보다 작은 정수이다.    문제 풀이 n이 1일 때부터 경우의 수를 구해봤다.n = 1일 때 경우의 수는 (1)로 1이다.n = 2일 때 경우의 수는 (1+1), (2)로 2이다.n = 3일 때 경우의 수는 (1+1+1), (1+2), (2+1), (3)으로 4이다.n = 4일 때 경우의 수는 (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (1+3), (3+1), (2+2)로 7이다. 위의 결과를 종합해봤을 때 dp를 경우의 수를 담는 배열이라고 생각하고,dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 라는 점화식이 유도된다...

백준 1351번 - 무한 수열 (골드 5)     문제 분석무한 수열 A는 다음과 같다.A0 = 1Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1) ( ⌊x⌋는 x를 넘지 않는 가장 큰 정수) N, P와 Q가 주어질 때, An을 구하는 문제다.  문제 풀이DP를 사용해서 An의 값을 저장해야겠다고 생각했다.dp[i] = A⌊i⌋ 라고 정의했다.dp[0] = 1로 초기화한 뒤 i는 1부터 N까지 dp[i] = dp[i / P] + dp[i / Q] 공식을 이용해서 값을 저장해주고 dp[N]을 출력해주는 방식으로 문제를 풀었다.  처음 시도메모리 초과가 났다.#include #include #include #include using namespace std;using ll = long long;int ma..

백준 2225번 - 합분해 (골드)     문제 분석0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제다.같은 수를 여러 번 사용해도 되고(중복 허용) 순서가 바뀌는 경우(순서 있음)도 센다.  처음 시도중복 순열을 이용해서 문제를 풀었더니 시간 초과가 났다.#include #include using namespace std;int N, K, caseCnt = 0;vector used;vector selected;void Pick(int sIdx){ if (sIdx == K) { int sum = 0; for (int& i : selected) sum += i; if (sum == N) caseCnt++; return; } for (int i = 0; i > N >..

백준 9251번 - LCS (골드 5)     문제 분석두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.  문제 풀이먼저, 예시로 주어진 두 문자열을 비교해보자.아래 표는 해당 문자까지의 최대 길이를 저장한 배열이다. ACAYKPC011111A112222P112223C122222A123333K123344 행과 열을 비교하며 표를 채울 수 있다.'A'와 'C'를 비교하면 LCS는 0이 된다.'AC'와 'C'를 비교하면 LCS는 'C'로 1이 된다.'ACA'와 'C'를 비교하면 LCS는 'C'로 1이 된다. 이런 식으로 표를 채워가면 아래 공식을 발견할 수 있다.두 문자가 같을 때는 문자를 추가하기 전 ..

백준 11053번 - 가장 긴 증가하는 부분 수열 (실버 2)     문제 분석수열 A가 주어졌을 때, 가장 긴 증가하는 부분 순열의 길이를 구하는 문제이다.예를 들어, 수열 A = { 10, 20, 10, 30, 20, 50 } 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10, 20, 10, 30, 20, 50 } 이고, 길이는 4이다.  문제 풀이핵심 아이디어는 DP를 이용해서 해당 수까지의 최대 길이를 저장해주고, 최대 길이를 구하는 것이다.예를 들어, 수열 A = { 10, 20, 30, 25, 10, 30, 40, 50 } 가 있다고 하자. 첫 번째 10보다 작은 숫자가 없었으므로 최대 길이는 1이 된다.두 번째 20보다 작은 숫자인 10의 최대 길이가 1이므로 +1을 한 2가 최대 길..

백준 1003번 - 피보나치 함수 (실버 3)     문제 이해N번째 피보나치 수를 구할 때 0과  1이 각각 몇 번 출력되는지 구하는 문제이다.  문제 해결 방법시간 제한이 0.25초라서 재귀 함수로 풀게 되면 시간 복잡도가 O(2ⁿ)이 되므로 시간 초과가 난다.동적 프로그래밍 (DP)을 사용하면 dp 배열을 한 번만 채우면 되므로 시간 복잡도가 O(N)이 된다.따라서 DP를 이용해서 문제를 풀면 된다. 먼저, 점화식을 사용해서 0과 1이 출력된 횟수를 구해준 다음 N일 때 값을 출력하면 된다.1. dp[0][n] = fibonacci(n)을 호출했을 때 0이 호출된 횟수, dp[1][n] = fibonacci(n)을 호출했을 때 1이 호출된 횟수2. 점화식 dp[0][n] = dp[0][n - 1] ..