[BOJ] 15988번 - 1,2,3 더하기 3
문제설명 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 사고과정 1,2,3 더하기 문제랑 동일한 점화식인 문제이다. 단, 주어지는 데이터 범위만 차이가 있다. 주어진 범위가 백만이라 입력 데이터를 받을 때 sys 라이브러리를 활용했다. 점화식은 다음과 같다. $dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$ 참고로 n = 3일 때까지는 직접 경우의 수를 구해주어서 DP 테이블에 넣어주어야 한다. 그러므로 n이 1,2,3일 때는 개별로 처리하도록 해준다. 만약 안해주면 Inde..
[BOJ] 14002번 - 가장 증가하는 부분 수열 4
문제설명 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 사고과정 아무거나 수열 출력하는 부분에서 매우 고생했다.. 오히려 문제의 난이도가 여기에서 올라가는 것 같다.. 반례에 자꾸 걸려서 구글링을 했는데 구글링한 것 중에서도 간결한 코드를 찾기가 쉽지 않았다. 그러던 중 하나의 훌륭한 블로그 글을 발견하고! 해당 풀이를 참조했다!(감사합니다 :) 풀이(스스로 못..
[BOJ] 11053번 - 가장 긴 증가하는 부분 수열
문제설명 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 사고과정 이전에 이코테 문제에서 풀어본 병사 배치하기 문제를 통해서 LIS(가장 긴 증가하는 부분 수열) 알고리즘에 대해 배웠었다. git 팀 노트에 적어놓긴 했었지만 다시 회상할 겸 소스코드를 보지 않고 직접 머릿속으로 구현하려 했다. LIS 알고리즘 개념은 여기를 참고하자. 풀이 a = int(input()..
[BOJ] 15990번 - 1, 2, 3 더하기 5
문제설명 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 사고과정 저번 1,2,3 더하기 문제와 난이도가 매우 달랐던 것 같다.. DP 테이블을 1차원으로 정의하고 어떻게든 규칙을 찾아보려 했지만 실패했다. 핵심 풀이는 2차원으로 DP 테이블을 운영하는 것이었고 또 하나는 다이나믹 프로그래밍의 핵심인 "뒤의 입장에서 생각" 하기 였다. 어떤 뒤의 입장이냐.. 바로 1, 2, 3 합으로만 이루어진 것을 찾는 것이므로 특정한 수 n을 1, 2, 3의 합으로 만들 때, 그 연산에 사용된 마지막 피연산..
