다이나믹 프로그래밍
-
[Baekjoon Online Judge] 19947번: 투자의 귀재 배주형문제 풀이/Baekjoon Online Judge 2021. 3. 29. 16:19
19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 요구사항 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. - 1년마다 5%의 이율을 얻는 투자 (A) - 3년마다 20%의 이율을 얻는 투자 (B) - 5년마다 35%의 이율을 얻는 투자 (C) 투자를 할 때에는 다음과 같은 주의점이 있다. - 투자의 기한(1년, 3년, 5년)을 채우는 시점에 이율이 반영되며, 그 사이에는 돈이 늘어나지..
-
[Baekjoon Online Judge] 1010번: 다리 놓기문제 풀이/Baekjoon Online Judge 2021. 3. 5. 22:09
1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 요구사항 - 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. - 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) - 재원이는 서쪽의 사이트와..
-
[Baekjoon Online Judge] 1620번: LCS 2문제 풀이/Baekjoon Online Judge 2021. 2. 15. 22:51
9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 요구사항 - LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. - 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 - 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 - 첫째 줄에 입력..
-
[Baekjoon Online Judge] 14501번: 퇴사문제 풀이/Baekjoon Online Judge 2021. 2. 13. 12:35
14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 요구사항 - 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. - 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. - 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표가 입력으로 주어졌다고 가정한다. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 - 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수..
-
[Baekjoon Online Judge] 9461번: 파도반 수열문제 풀이/Baekjoon Online Judge 2021. 2. 13. 11:14
9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 요구사항 - 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. - 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. - N이 주어졌을 때, P(N)을 구한다. 입력 - 첫째 줄에 테스트 케이스의 개수 T가 주어..
-
[Baekjoon Online Judge] 10942번: 팰린드롬?문제 풀이/Baekjoon Online Judge 2021. 2. 12. 14:56
10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 요구사항 - 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. - 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다(1) 또는 아니다(0)를 말해야 한다. 입력 - 첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다. - 둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거..
-
[Baekjoon Online Judge] 11727번: 2xn 타일링 2문제 풀이/Baekjoon Online Judge 2021. 2. 10. 15:58
11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 요구사항 - 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성한다. 입력 - 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 - 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 2021/01/30 - [문제 풀이/다이나믹 프로그래밍] - [Baekjoon Online Judge] 11726번: 2xn 타일링 [Baekjoon Online Judge] 11726번: 2xn 타일링 11726번: ..
-
[Baekjoon Online Judge] 10844번: 쉬운 계단 수문제 풀이/Baekjoon Online Judge 2021. 2. 6. 17:39
10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 요구사항 - 인접한 모든 자리수의 차이가 1인 수를 계단 수라고 한다. - 수의 길이 n이 주어지면 계단 수가 몇 개 인지 구한다. - 수는 0으로 시작할 수 없다. 입력 - 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 - 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 자리 수가 1일 때 계단 수는 1, 2, 3, 4, 5, 6, 7, 8 9로 9개 이다. 자리 수가 2일 때 계단 수는 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98..