방앗간 개발자

문제 출처: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/1652

일 년 동안 세계일주를 하던 영식이는 여행을 하다 너무 피곤해서 근처에 있는 코레스코 콘도에서 하룻밤 잠을 자기로 하고 방을 잡았다.

코레스코 콘도에 있는 방은 NxN의 정사각형모양으로 생겼다. 방 안에는 옮길 수 없는 짐들이 이것저것 많이 있어서 영식이의 누울 자리를 차지하고 있었다. 영식이는 이 열악한 환경에서 누울 수 있는 자리를 찾아야 한다. 영식이가 누울 수 있는 자리에는 조건이 있다. 똑바로 연속해서 2칸 이상의 빈 칸이 존재하면 그 곳에 몸을 양 옆으로 쭉 뻗으면서 누울 수 있다. 가로로 누울 수도 있고 세로로 누울 수도 있다. 누울 때는 무조건 몸을 쭉 뻗기 때문에 반드시 벽이나 짐에 닿게 된다. (중간에 어정쩡하게 눕는 경우가 없다.)

만약 방의 구조가 위의 그림처럼 생겼다면, 가로로 누울 수 있는 자리는 5개이고, 세로로 누울 수 있는 자리는 4개 이다. 방의 크기 N과 방의 구조가 주어졌을 때, 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다.

첫째 줄에 가로로 누울 수 있는 자리와 세로로 누울 수 있는 자리의 개수를 출력한다.

문제를 이해만 한다면 복잡한 알고리즘 없이 몇가지 조건만 가지고 풀 수 있는 문제입니다.

예제로만 보면 설명이 애매한 부분이 있어 그림을 하나 첨부합니다.

위 그림의 가로로 누울 수 있는 부분 첫 번째 줄을 보면 벽 하나를 두고 양 옆으로 2칸씩 있기 때문에 한 줄에 누울 수 있는

자리는 2개가 됩니다. 전 처음에 이부분을 생각하지 않고 풀었다가 뒤늦게 깨닫고 수정했습니다. 

이 부분만 주의하면서 임의의 cnt변수를 하나 만든뒤 2차원 배열을 한 줄씩 탐색하며 빈 방이 나오면 1씩 증가시키다 

cnt == 2가 되면 누울 수 있는 자리라 판단하여 체크해주고 계속 탐색하다가 벽이 나올경우 cnt 변수를 0으로 초기화 

시켜주면 됩니다. 

코드는 짧고 이해하기 어렵지 않으므로 전체 코드를 한번에 올리겠습니다.