문제 링크 1. 기본적인 피보나치 수열. 2. $N=3,4,5$ 정도까지 직접 써보면 피보나치 수열을 이룬다는 것을 쉽게 알 수 있다. 개수를 15746으로 나눈 나머지로 저장한다는 문제 조건을 잊으면 안 된다. 사실 처음에는 재귀 함수를 사용해서 풀어봤는데, 스택 오버플로우가 발생하였다. N이 최대 백만이니 재귀는 비효율적이라는 것을 알 수 있다. 3. import java.util.Scanner; public class Main { static int[] dp; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new int[n + 1..
DP
문제 링크 1. LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제 2차원 DP 배열을 구성하면 될 것이라 생각했는데, 비효율적으로 구성하다 보니 코드 짜기가 막막했다. 좀 더 획기적인 방법이 필요했다. 어렵다. 지친다. 2. dp 배열의 행은 비교당할 문자열 (CAPCAK ), 열은 비교할 문자열 (ACAYKP ) 이다. dp[i][j] 는 문자열 b의 i번째, 문자열 a의 j번째 위치까지 구해진 LCS의 값이다. ACAYKP CAPCAK dp[3][2] = 1 ACAYKP CAPCAK dp[3][3] = 2 ACAYKP CAPCAK dp[3][6] = 3 j번째 알파벳이 i번째 알파벳과 같으면 1이 증가한다. 어떤 값에서 1이 증가할까? 고민해보면, 그 전까지의 공통부..
문제 링크 1. 1시간 소요. 점화식 세우는 아이디어는 금방 떠올라서 코드를 쭉쭉 써내려 갔다. 그러나 오답처리가 되어 질문 검색을 통해 반례를 찾아서 수정하는 데에 오랜 시간이 걸렸다. 점화식을 어떠한 식으로 세워야할 지 감을 잡았다는 점에서 만족한다. 2. 처음 풀었던 코드의 반례는 $2, 1, 5, 6, 7$ 이였다. 기댓값은 $20$ 인데, 나는 $19$ 가 나왔다. $2$ 부터 선택하는 것이 최댓값인데 이를 고려하지 않았던 것이다. dp배열은 해당 index 까지의 증가 부분 수열 합의 최댓값이다. 이해가 안 되면 다음을 명심하자. DP문제는 큰 문제를 작은 문제로 쪼개어 생각하자 문제의 메커니즘은 완성된 dp배열을 보면서 설명하고자 한다. dp[3]을 계산하려면, 1. arr[3] 이전의 원소..
문제 링크 1. 1시간 소요. 노트에 대략적인 경우의 수를 모두 적어 점화식을 쉽게 구했으나, 오답이었다. 맞게 푼 것 같은데 잘못된 부분을 도저히 못 찾겠어서 다른 사람의 질문을 참고했다. 32의 결과값은 2가 나와야 하는데, 나는 5가 나왔다. 나는 $25+4+1+1+1$ 으로 계산했지만, $16+16$ 이라는 최소 개수가 존재한다. 이를 반영해서 코드를 수정했고 정답 메시지를 받았다. 비록 오류를 스스로 잡지는 못했지만 해설을 보지 않고 푼 것에 만족한다. 대신 코드가 조금 지저분한 것은 사실이다. 2. $1 = 1$ $2 = 1+1$ $3 = 1+1+1$ $4 = 4$ $5 = 4+1$ $6 = 4+1+1$ $7 = 4+1+1+1$ $8 = 4+4$ 규칙이 보이는가? 8을 예로 들면, 8과 가장 ..
문제 링크 1. 1시간 고민하고 점화식을 세우지 못해 해설을 참고했다. dp문제는 정말 너무 어려운 것 같다.. 해설 이해하는 것도 시간이 꽤 걸렸다. 2. 두 가지 배열을 선언 한다. coin배열은 사용할 수 있는 동전의 종류이고, dp배열은 동전을 사용해서 합이 index원이 되도록 하는 경우의 수를 나타낸다. 가장 작은 동전을 사용했을 때 각 dp배열의 각 index원을 만드는 경우의 수를 계산하고, 그 다음 동전을 사용했을 때 경우의 수를 여기에 누적하는 방식으로 진행을 한다. 예를 들어, 1을 사용해서 2를 만드는 경우의 수는 1+1로 총 1가지 이다. 2를 사용해서 2를 만드는 경우의 수는 2로 총 1가지 이다. 1을 사용해서 3을 만드는 경우의 수는 1+1+1로 총 1가지 이다. 2를 사용해..
https://www.acmicpc.net/problem/11057 1. 무슨 문제인지는 모르겠지만 전에 풀었던 문제와 유사하다는 느낌을 받았다. 점화식 규칙을 찾으려고 공책에 $n=3$ 일 경우까지 모두 적어보았다. 2. dp배열을 2차원으로 구성하는 것이 핵심이다. 행은 n을 나타내고 열은 0부터 9까지의 수를 나타내는데, 각 배열의 원소는 해당 열로 끝나는 숫자로 나타낼 수 있는 경우의 수이다. 위 그림은 $n=3$일 경우 만들어지는 dp 배열이다. 이를 점화식으로 나타내면 다음과 같다. dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) 왜 이렇게 점화식을 세웠는지 다음 그림을 통해 알아보자. $(3, 2)$ 에서 주황색 부분은 $(2, 2)$의 원소 맨 앞에 $0$을 붙여준..
https://www.acmicpc.net/problem/9465 1. 큰 수를 먼저 선택하면 될까? 반례가 존재하고 DP 문제이기에 잘못된 접근 방식이었다. 큰 문제를 작은 문제로 쪼개어 점화식을 세워야 했는데, 어려웠다. 2. 떼어낼 스티커를 선택하는 방법에는 두 가지가 있다. 1. 왼쪽 대각선에 위치한 스티커를 떼어냈을 경우 2. 왼쪽 왼쪽 대각선에 위치한 스티커를 떼어 냈을 경우 이 두 가지 경우 중 최대값을 선택하여 dp 배열에 저장한다. 여기서 이해가 어려웠던 것은 (1, 3)을 선택하는 경우도 존재 하지 않는가? 였다. 이에 대한 답은, (0, 4)에서 이미 이를 고려했기에 고려하지 않아도 된다. 이 두 가지 방법을 점화식을 나타내면 다음과 같다. dp[0][j] = Math.max(dp[1..
