https://www.acmicpc.net/problem/15486 어… 그런데 이 문제 퇴사 백준 14501번 DP 이것과 똑같이 나와서 뭐가 다른지 찾아보았더니 퇴사 1의 경우 N의 크기가 1부터 15였다면 퇴사 2는 1부터 1500000까지 입력크기가 다르다는 점입니다. 그래서 퇴사 1의 경우 DP가 아니라 완전탐색으로 문제를 풀 수 있...
파도반 수열 백준 9461번 DP
https://www.acmicpc.net/problem/9461 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N...
가장 긴 증가 부분 수열 백준 11053번 DP
https://www.acmicpc.net/problem/11053 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 바...
가장 큰 증가 부분 수열 백준 11055번 DP
https://www.acmicpc.net/problem/11055 문제 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, ...
연속합 백준 1912번 DP
https://www.acmicpc.net/problem/1912 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주...
이친수 백준 2193번 DP
https://www.acmicpc.net/problem/2193 문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. ...
2xn 타일링 2 백준 12852번
https://www.acmicpc.net/problem/11727 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 평범한? DP문제입니다. 다만 점화식을 구하는데 4번째….가 11가지 케이스가 나오는데 9개로보고 한참을 고민했습니...
1로 만들기 2 백준 12852번 DP
https://www.acmicpc.net/problem/12852 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 ...