방앗간 개발자

문제 출처:https://www.acmicpc.net/problem/10942

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

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

각 질문은 두 정수 S와 E로 나타낼 수 있으며, 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을 출력한다.

문제를 처음 읽었을때 딱히 이해가 어렵지 않고 풀이 방법도 어렵지 않을 것 같습니다. 

그러나 문제를 풀어보기 시작하면 당연하게도 시간이 발목을 잡습니다. 

수열의 최대 크기가 2,000이고 질문의 개수가 최대 1,000,000 이므로 S,E가 주어졌을때 일일히 for문을 돌려가며 팰린드롬

을 판별하면 절대 제한 시간인 0.5초 안에 문제를 풀지 못합니다. 따라서 동적 계획법(다이나믹 프로그래밍)을 이용하여 O(n)

의 시간복잡도를 가지는 팰린드롬 계산을 최대한 O(1)로 만들어야 문제가 풀리게 됩니다.

그럼 이제 이 문제에 대하여 어떻게 동적 계획법을 적용하는지 설명 하겠습니다. 

핵심은 팰린드롬의 특징을 이용하는것인데 어떤 수열 N과 S,E가 주어졌을때 이 S,E가 팰린드롬이라면 S<=E라는 조건 안에

서 (S+1,E-1) (S+2,E-2) (S+3,E-3)....... 모두 팰린드롬이 된다는 것입니다. 

이 점을 이용하여 DP[2001][2001]배열을 하나 만든 뒤 S,E가 주어졌을때 팰린드롬이라면 DP[S][E], DP[S+1][E-1], DP[S+2][E-2]

DP[S+3][E-3]..... 전부 팰린드롬이라고 체크를 해준다면 나중에 이 범위에 속해있는 S,E가 주어졌을때 반복문을 돌리지 않고 

즉시 팰린드롬인지 아닌지 알 수 있게 됩니다.

그림으로 설명하면 다음과 같습니다.

수열 N과 S,E가 주어졌을때 S,E가 팰린드롬인지 구해주는 함수입니다.

반복을 모두 마치고 리턴하면 팰린드롬 중간에 반복이 중단되면 팰린드롬이 아닙니다.

문제 출처:https://www.acmicpc.net/problem/2096

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

첫째 줄에 얻을 수 있는 최대 점수와 최소 점수를 띄어서 출력한다.

본문에는 나와있지 않지만 출처에 들어가서 문제를 확인해보면 메모리 제한이 4MB 밖에 안된다는 것을 알 수 있습니다. 

따라서 들어오는 입력을 전부 다 저장한뒤 문제를 푸는 것이 아니라 입력이 한 줄씩 들어올때 바로바로 계산을 해서 갱신을 

해주어야 합니다.

즉시 계산을 하는 방법은 임의의 배열(DP)를 만들어 입력이 들어올때 문제의 조건에 맞추어 최대 점수와 최소 점수를 구해 

배열에 저장해주면 됩니다. 

이해를 돕기 위하여 출처의 예제에 나와있는 입력에 대해서 그림으로 설명하겠습니다.

입력: 3                                출력: 18    6

   1    2    3

   4    5    6

   4    9    0

예제 입력에서 최대 점수를 구하는 방법입니다.

처음엔 DP배열에 아무 데이터도 없기 때문에 입력값 그대로 넣어줍니다.

두 번째 부터 입력값과 DP배열을 비교하여 DP배열을 수정해줍니다. 

지금 그림의 경우는 최대 점수를 구하기 때문에 더해서 비교했을때 더 큰 값으로 DP배열을 갱신 해줍니다.

최종적으로 구해진 DP배열에서 가장 큰 값을 출력해주면 최대 점수를 구할 수 있습니다.

최소 점수는 반대로 DP배열을 갱신해줄때 더 작은 값으로 갱신하고 최종적으로 만들어진 DP배열에서 

가장 작은 값을 선택하면 됩니다.

전체 소스입니다.

문제 출처:https://www.acmicpc.net/problem/2240

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

저는 이 문제의 점화식을 구하지 못하여서 재귀를 이용하여 풀었습니다. 단 재귀 호출을 사용할경우 피보나치 재귀처럼 중복

호출이 매우 많아 100% 시간초과가 뜨기 때문에 자두의 각 상태에 대한 값을 저장 해 줄수 있는 DP 배열을 하나 만들어 중복

호출을 최대한 줄여 문제를 풀었습니다.

이 문제에서 한 가지 주의 할 점은 자두가 시작하자마자 옆으로 움직여 움직임 횟수를 1 줄이고 1번 나무 아래에서도 시작 할 

수 있다는 점입니다. 따라서 저는 메인 함수에 자두가 1번,2번 나무에서 시작하는 경우를 각각 호출 해 주었습니다. 

코드에 대한 설명은 주석으로 해 두었습니다.

전체 코드입니다.