CodeDrive

문제:

풀이방법:

y를 만드는 것이 목적이므로 y 길이를 가지고 있는 DP 배열을 만들어서 연산을 수행하도록 한다.

DP에 연산을 하면서 연산 횟수를 채워나가면 되는데, 최소 연산 횟수를 구해야 하므로 min 연산을 추가로 하도록 한다. 즉, 특정 숫자 x에 접근할 수 있는 방법은 여러가지가 있을텐데 그 중 가장 작은 횟수만 선택하는 것이다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제:

기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.

기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.

1. 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다.
2. 소형 기관차 3대를 이용하여 최대한 많은 손님을 목적지까지 운송하도록 한다. 각 객차 마다 타고 있는 손님의 수는 미리 알고 있고, 다른 객차로 손님들이 이동하는 것은 허용하지 않는다.
3. 각 소형 기관차는 번호가 연속적으로 이어진 객차를 끌게 한다. 객차는 기관차 바로 뒤에 있는 객차부터 시작하여 1번 부터 차례로 번호가 붙어있다.

예를 들어 기관차가 끌고 가던 객차가 7칸이고, 소형 기관차 1대가 최대로 끌 수 있는 객차 수는 2칸이라고 하자. 그리고 1번 부터 7번까지 각 객차에 타고 있는 손님의 수가 아래 표와 같다고 하자. 괄호속에 있는 숫자는 객차 번호를 나타낸다.

(1)(2)(3)(4)(5)(6)(7)

소형 기관차 3대는 각각 1-2번, 3-4번, 그리고 6-7번 객차를 끌고 가면 손님 240명을 운송할 수 있고, 이보다 많은 수의 손님을 운송할 수 없다.

기관차가 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수, 그리고 소형 기관차가 최대로 끌수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있는 손님의 수는 100명 이하이고, 입력되는 숫자들 사이에 빈칸이 하나씩 있다. 셋째 줄에는 소형 기관차가 최대로 끌 수 있는 객차의 수가 입력된다. 그 수는 기관차가 끌고 가던 객차 수의 1/3보다 적다.

출력:

한 줄에 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 출력한다.

풀이방법:

점화식을 생성해서 DP로 해당 문제를 풀 수 있다. DP는 다음과 같이 정의한다.

• DP[N][M]: 소형기관차 N대를 운행할 때 M번째 객차를 선택했을 때 최대로 운송 가능한 손님 수

따라서 점화식은 다음과 같다.

DP[N][M] = max( DP[N][M-1], DP[N-1][M-limit] + sum(numbers[M-limit+1:M+1]))

점화식을 사용해서 문제의 예제에 대입하면 다음과 같이 DP 테이블을 채워나갈 수 있다.

예시를 참고하여 어떠한 원리로 동작하는지 알아보도록 한다.

• DP[1][2] = max(DP[1][1], DP[0][2-2] + sum(numbers[2-2+1:2+1]))
  • DP[1][1], DP[0][0]는 둘 다 0이기때문에, sum만 계산하면 되므로 35+45다.
• DP[3][6] = max(DP[3][5], DP[2][6-2] + sum(numbers[6-2+1:6+1])
  • DP[3][5]는 0이므로, 뒷 항에 의해 결된다. DP[2][6-2]는 75+60이고, 여기에 30+45를 더해준다.

점화식이 의미하는 것은 현재 운행하고 있는 소형 기관차가 이전의 객차를 변경없이 유지했을 때(DP(N][M-1]), N번째 소형 기관차를 객차를 선택하기 전에 N-1번째 소형기관차를 유지하면서(DP[N-1][M-limit]) N번째 소형기관차가 M번째 소형기관차를 선택했을 때(sum(numbers[M-limit+1:M+1]))를 비교하는 것이다.

문제링크:

https://www.acmicpc.net/problem/2616

문제:

동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되어 있는 모든 문자열은 N개의 "a"와 M개의 "z"로 이루어져 있다. 그리고 다른 문자는 없다. 사전에는 알파벳 순서대로 수록되어 있다.

규완이는 사전을 완성했지만, 동호는 사전을 완성하지 못했다. 동호는 자신의 과제를 끝내기 위해서 규완이의 사전을 몰래 참조하기로 했다. 동호는 규완이가 자리를 비운 사이에 몰래 사전을 보려고 하기 때문에, 문자열 하나만 찾을 여유밖에 없다.

N과 M이 주어졌을 때, 규완이의 사전에서 K번째 문자열이 무엇인지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 N, M, K가 순서대로 주어진다.

출력:

첫째 줄에 규완이의 사전에서 K번째 문자열을 출력한다. 만약 규완이의 사전에 수록되어 있는 문자열의 개수가 K보다 작으면 -1을 출력한다.

풀이방법:

해당 문제는 다음과 같은 알고리즘으로 해결하도록 한다.

1. n개의 a m개의 z가 있다고 했을 때, a를 하나 제거했을 때의 경우의 수를 구한다.

2. 이 갯수가 k보다 크다면 a를 먼저 배치한다.

2-1. 이 갯수가 k보다 작다면 z를 먼저 배치하고, k에서 1에서 구한 값을 빼준다.

3. n이나 m 둘 중 하나가 0이 될 때까지를 이를 반복하고, 남은 n과 m이 있다면 다 이어붙이고 종료한다.

문제링크:

https://www.acmicpc.net/problem/1256

문제:

KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 위해 목적지까지 번호순서대로 일렬로 서서 걸어가도록 하였다. 이동 도중에 보니 아이들의 번호순서가 바뀌었다. 그래서 선생님은 다시 번호 순서대로 줄을 세우기 위해서 아이들의 위치를 옮기려고 한다. 그리고 아이들이 혼란스러워하지 않도록 하기 위해 위치를 옮기는 아이들의 수를 최소로 하려고 한다.

예를 들어, 7명의 아이들이 다음과 같은 순서대로 줄을 서 있다고 하자.

3 7 5 2 6 1 4

아이들을 순서대로 줄을 세우기 위해, 먼저 4번 아이를 7번 아이의 뒤로 옮겨보자. 그러면 다음과 같은 순서가 된다.

3 7 4 5 2 6 1

이제, 7번 아이를 맨 뒤로 옮긴다.

3 4 5 2 6 1 7

다음 1번 아이를 맨 앞으로 옮긴다.

1 3 4 5 2 6 7

마지막으로 2번 아이를 1번 아이의 뒤로 옮기면 번호 순서대로 배치된다.

1 2 3 4 5 6 7

위의 방법으로 모두 4명의 아이를 옮겨 번호 순서대로 줄을 세운다. 위의 예에서 3명의 아이만을 옮겨서는 순서대로 배치할 수가 없다. 따라서, 4명을 옮기는 것이 가장 적은 수의 아이를 옮기는 것이다.

N명의 아이들이 임의의 순서로 줄을 서 있을 때, 번호 순서대로 배치하기 위해 옮겨지는 아이의 최소 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 아이들의 수 N이 주어진다. 둘째 줄부터는 1부터 N까지의 숫자가 한 줄에 하나씩 주어진다. N은 2 이상 200 이하의 정수이다.

출력:

첫째 줄에는 번호 순서대로 줄을 세우는데 옮겨지는 아이들의 최소 수를 출력한다.

풀이방법:

 N명의 아이들을 번호 순서대로 배치하기 위해 최소의 움직임을 구한다는 것은 LIS 문제와 같다. 가장 긴 부분 수열을 찾고, 그 수열에 속하지 않은 아이들만 움직이는 것이 최소 움직임일 것이기 때문이다.

 따라서 DP를 사용한 LIS 문제를 풀고, N에서 그 값을 빼주도록 한다.

문제링크:

https://www.acmicpc.net/problem/2631

문제:

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력:

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

풀이방법:

DP를 사용해서 해당문제를 풀도록 한다. 이 때, N이 6번까지는 ctrl+A,C,V를 사용하는 것보다 하나를 더 추가하는 것이 더 이득이기 때문에 하나씩 추가하도록 한다. 복사 붙여넣기를 하기 위해서는 최소 3개의 명령어를 사용해야 한다. 따라서 ACV, ACVV, ACVVV, ...와 같은 방법으로 붙여넣기를 진행할 수 있다. 하지만 붙여넣기는 최대 3번만 사용해도 최댓값을 구할 수 있기 때문에 ACV, ACVV, ACVVV 와 같은 3개 경우에 대해서 DP를 진행하도록 한다.

점화식은 dp[i] = max(dp[i-3-j]*(2*j), dp[i])와 같다.

문제링크:

https://www.acmicpc.net/problem/11058

문제:

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력:

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이방법:

 이전 1, 2, 3 더하기 문제에서는 재귀형태로 문제를 풀었지만 이번에는 숫자의 범위가 크기 때문에 시간초과가 발생할 것이다. 따라서 이번에는 dp 배열을 사용하여 문제를 풀도록 한다. 

 점화식은 간단한 편이다. N을 만들기 위해서 N-3의 경우에서 3을 N-2의 경우에서 2를 N-1일 대는 1을 각각 더해주면 되기 때문이다. 즉, dp[N] = dp[N-1] + dp[N-2] + dp[N-3]과 같다.

1000000까지 dp를 만든 뒤에 N 값을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/15988

문제:

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력:

첫째 줄에 AN을 출력한다.

풀이방법:

 문제에서 명확하게 점화식이 주어졌기 때문에 다이나믹 프로그래밍을 사용하도록 한다. 하지만 주어진 조건의 N, P, Q이 매우 크기 때문에 list를 사용해서 구현을 한다면 메모리가 터지는 문제점이 있다. 따라서 최대한 쓰지 않는(비어있는) 값들을 줄이기 위해서 dict 자료형에다가 값들을 mapping 하도록 한다. 빠른 구현을 위해서 defaultdict을 사용해 초기화하는 과정을 간단하게 구현할 수 있도록 했다.

문제링크:

https://www.acmicpc.net/problem/1351

문제:

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력:

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

풀이방법:

 두 개의 LIS(가장 긴 증가하는 부분 수열)을 사용해서 풀면 된다. 한 LIS는 앞에서부터, 다른 LIS는 뒤에서부터 수행한다. 수행하면서 각 위치까지의 LIS의 길이를 저장해둔다.

두 배열(dp, dp2)에 LIS의 길이를 저장했으므로 이 둘을 zip으로 같이 탐색하면서 합이 가장 큰 경우를 답으로 출력하도록 한다. 즉, 이 말은 기준이 Sk를 기준으로 왼쪽과 오른쪽의 길이의 합을 더하는 것과 같으며, Sk는 최종적으로 두 번 더해지기 때문에 -1을 뺀 값이 정답이 된다.

문제링크:

https://www.acmicpc.net/problem/11054

문제:

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

예를 들어, < 그림 1 >과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다.

전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

출력:

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다.

풀이방법:

 A, B를 쌍으로 저장한 뒤에 A를 기준으로 정렬한다. 그리고 B 값들에 대해 가장 긴 증가하는 부분 수열을 찾으면 가장 적게 제거하고 전깃줄이 서로 교차하지 않게 만들 수 있다.

 가장 긴 증가하는 부분 수열을 찾는 방법은 많지만 이분 탐색을 사용한 방법(N*log(N))을 통해서 찾고, 전체 길이에서 답을 구했다.

참조 링크 : https://seungkwan.tistory.com/8

문제링크:

https://www.acmicpc.net/problem/2565

문제:

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력:

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

풀이방법:

 "팰린드롬인 수열이 있다면 양쪽 끝에 같은 수를 붙이면 그 수열도 팰린드롬이 된다" 라는 아이디어를 통해서 풀 수 있는 문제다.

 따라서 dp 테이블을 다음과 같이 구성한다.

- dp[i][j] -> 1 if i~j의 수열이 팰린드롬

- dp[i][j] -> 0 if i~j의 수열이 팰린드롬이 아님

초기 dp 테이블 구성을 위해 1개 혹은 2개로 이루어진 팰린드롬만 따로 확인하여 구성하도록 한다. 나머지 값들에 대해서는 2중 for를 사용해서 양 끝 인덱스를 할당하고, 그 값이 같으며 그 속안의 dp 값이 1이라면(팰린드롬이라면) 그 수열도 팰린드롬이기 때문에 1로 바꿔주도록한다.

 위 과정을 통해 모든 dp 값을 최신화했다면, M을 통해 명령어를 받아 그 dp 테이블 값을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/10942