방앗간 개발자

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

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

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

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

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

첫째 줄에 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력한다. 둘째 줄부터 한 줄에 하나씩 없애야 하는 전깃줄의 A전봇대에 연결되는 위치의 번호를 오름차순으로 출력한다. 만약 답이 두 가지 이상이라면 그 중 하나를 출력한다.

바로 전 게시글에서 이어지는 문제입니다.

이번에도 없애야 하는 전깃줄의 최소 개수를 출력하는데 플러스로 없애야 하는 전봇대의 위치까지 알아내야 합니다.

일단 전 게시글에서 알려준 방법으로 없애야 하는 전봇대의 최소 길이부터 구해봅시다.

LIS의 길이를 구하는 방법을 모른다면 (1365번: 꼬인 전깃줄) 를 보고 오시면 됩니다.

예시는 위 그림에 있는 수열[ 4, 2, 6, 7, 9, 1, 3, 10 ]을 그대로 쓰겠습니다. 

위 수열에 LIS알고리즘을 사용한다면 [ 3, 6, 7, 9, 10 ] 의 결과가 나옵니다 이 수열의 길이가 LIS의 길이가 됩니다. 

단 이 수열이 LIS을 구성하는 수열은 아닙니다 딱 보더라도 제일 앞에 있는 3은 원본 수열에서 뒤쪽에 있는 수입니다. 

따라서 LIS의 요소까지 구하려면 추가적인 연산을 해주어야 하는데 이제부터 그 방법을 설명 하겠습니다.

일단 기존에 하던대로 LIS알고리즘을 수행합니다 단 수행하면서 입력되는 수가 LIS배열의 몇 번째 칸에 들어가는지 기록 

할 배열이 하나 더 필요합니다. 그림으로 표현하면 아래와 같습니다.

이 구해진 Record배열의 제일 뒤부터 순차적인 내림차순 즉 Record 배열의 제일 마지막이 5 이므로 5, 4, 3, 2, 1순으로 

원본 배열의 인덱스에 맞춰 데이터를 추가해주면 LIS 의 요소를 구할 수 있습니다. 

최종적인 수열 [ 2, 6, 7, 9, 10 ] 이 LIS 요소까지 구성하는 수열이 됩니다.

문제의 정답은 LIS를 만들기 위해 없애야 하는 전봇대를 구하는 것 입니다. 

따라서 원본 수열에서 최종적으로 구해진 LIS의 요소들을 전부 빼고 남은 숫자들이 없애야 하는 전봇대가 됩니다.

전체 코드입니다.

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

<그림 1>과 같이 정사각형 모양을 한 여섯 종류의 색종이가 있다. ①번 색종이는 한 변의 길이가 1cm이고, 차례대로 그 길이가 1cm씩 커져, ⑥번 색종이의 한 변의 길이는 6cm가 된다.

주어진 색종이를 <그림 2>와 같이 가로, 세로의 길이가 각각 6cm인 판 위에 붙이려고 한다. 색종이를 붙일 때는 색종이가 판의 경계 밖으로 삐져 나가서는 안되며, 색종이가 서로 겹쳐서도 안 된다. 또한 하나의 색종이는 하나의 판에만 붙여야 한다.

각 종류별로 색종이의 장수가 주어질 때, 그 색종이를 모두 붙이기 위해서 위와 같은 판이 최소 몇 개가 필요한지 구하는 프로그램을 작성하시오.

첫째 줄부터 여섯째 줄까지 각 종류의 색종이의 장수가 ①번부터 ⑥번까지 차례로 주어진다. 각 종류의 색종이의 장수는 최대 100이다.

첫째 줄에 필요한 판의 최소 개수를 출력한다.

가장 큰 색종이부터 판에 붙여주면서 남는 공간에도 들어갈수 있는 가장 큰 색종이를 넣어주는 식으로 문제를 풀었습니다. 

판의 크기가 크지 않고 색종이의 종류도 얼마 안되어서 경우의 수를 전부 계산하여 그림으로 나타내면 

일단 6번 색종이는 판에 꽉 차므로 다른 색종이를 더 넣을 수 없습니다.

5번 색종이는 

위와같이 1개만 들어갈 수 있고 나머지 공간은 전부 1번 색종이로 채울 수 있습니다.

4번 색종이는

위와같이 1개만 들어갈 수 있고 나머지 공간에 2번 색종이가 최대 5개 들어갈 수 있습니다.

2번 색종이가 5개 이하라면 나머지 공간엔 1번 색종이로 채워주면 됩니다.

3번 색종이가 경우의 수가 여러가지 있는데

이렇게 전부 3번 색종이로만 채워진다면 최대 4개가 채워집니다.

3번 색종이가 3개만 채워진다면 나머지 공간에 2번색종이가 1개 들어갈 수 있고

나머지 공간은 1번 색종이로 채워줍니다.

3번 색종이가 2개만 채워진다면 2번 색종이는 최대 3개 채워지고 

나머지 공간은 1번 색종이로 채워줍니다.

3번 색종이가 1개만 채워지면 2번 색종이는 최대 5개 채워지고

마찬가지로 남는 공간은 1번 색종이로 채워줍니다.

2번 색종이는

위와같이 최대 9개까지 채울 수 있습니다.

남은공간이 있다면 1번 색종이로 채우면 됩니다.

위와같은 과정을 거치고도 1번 색종이가 남아있다면 한판에 최대 36개가 들어갈 수 있으니 

남아있는 1번 색종이의 수에 맞춰 판을 추가해줍니다.

이런방식으로 주어진 색종이에서 최소 몇개의 판이 필요한지 구할 수 있습니다. 

아래는 전체 소스입니다.

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

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

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

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

문제 자체는 DFS나 BFS를 이용하여 조건에 맞추어 인구 이동이 가능한 영역을 구하고 이 영역 안에서 인구 이동을 시킵니다.

이 인구 이동을 더 이상 불가능 할때까지 계속 반복하며 인구이동 발생 수를 체크만 해주면 되는 비교적 간단한 문제인데 

저는 문제에서 말하는 '인구 이동'을 잘 못 이해하여 문제를 푸는데 한참 걸렸습니다.

제가 헷갈린 인구 이동은 아래와 같습니다.

L = 10, R = 50

이런 형태로 입력이 주어졌다고 합시다.

주어진 배열에 대하여 인구 이동이 가능한 영역을 위와같이 구해줍니다.

조건에 맞게 배열을 변형시켜준 뒤 인구 이동 횟수를 1 증가시킵니다. 

변형된 배열에 맞추어 한번 더 인구 이동이 가능한 영역을 구합니다.

여기서 한 구역을 조건에 맞추어 바꿔주었는데 이 때 인구 이동 횟수를 1 증가시키면 안됩니다. 

이렇게 모든 영역을 전부 다 바꿔준 뒤에야 인구 이동 횟수를 1 증가시켜주어야 합니다.

저는 처음에 구역 한개가 바뀔때마다 인구 이동 횟수를 증가시키는 줄 알고 한참을 고생했습니다.

이 부분만 주의해서 풀면 그렇게 어렵지 않게 풀이가 가능할거라 생각됩니다.

그리고 더 이상 인구 이동이 가능하지 않아서 프로그램을 종료하는 조건은 저의 경우 아래와 같은

형식으로 풀었습니다.

위의 배열에 대하여 영역을 구했을때 똑같은 크기의 배열을 하나 더 만들어 아래처럼 숫자로 각 구역을 

표시 해 주었습니다. 따라서 어떤 배열이 주어졌을때 아래처럼 영역을 숫자로 나타낸 배열이 

이와 같은 형식을 나타낸다면 모든 구역이 전부 독립적인 영역을 가진다는 의미이므로 이 때 프로그램을 

종료시켜 주었습니다.

전체 코드입니다.

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

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

이런 문제를 처음 풀어본다면 대체 어떻게 접근해야 하는지 감이 안잡힐 수도 있지만  

몇가지 예시를 들어 문제를 풀어보면 한 가지 패턴을 찾을 수 있습니다. 

입력: 7    3    1    2    0    6    8    9    4    10 

이런 전선 입력이 주어졌다면 여기서 꼬이지 않고 전선을 잘라내는 방법은 

7    3    1    2    0    6    8    9    4    10

빨간색으로 칠한 전선을 잘라내는 것 입니다. 전선을 잘라내고 남아있는 전선(1, 2, 6, 8, 9, 10)을 보면 한 가지 패턴이 있는데 

바로 '증가하는 수열' 이라는 겁니다.

따라서 이 문제는 어떤 임의의 수열이 주어졌을 때, 이 수열에서 몇 개의 수를 제거하여 만들 수 있는 부분수열 중 오름차순으

로 정렬된 가장 긴 수열을 찾는 최장 증가 부분 수열(LIS : Longest Increasing Subsequence)알고리즘을 이용하여 푸는 문제

입니다.

이 LIS알고리즘은 O(n^2)과 O(n log n)의 시간이 걸리는 알고리즘이 각각 있지만 이 문제에선 최대 입력이 100,000이므로 

O(n^2)의 알고리즘을 사용하면 시간초과에 걸립니다. 따라서 저는 O(n log n)의 알고리즘을 소개하고 문제를 풀겠습니다.

O(n log n)의 알고리즘에선 이진탐색을 약간 변형한 알고리즘인 Lower bound를 사용하게 됩니다. 

입력값은 위에 예시로 든 수열을 그대로 사용하겠습니다.

입력: 7    3    1    2    0    6    8    9    4    10

1. 벡터를 하나 만들어 줍니다.

2. 수열을 처음부터 검사하는데 현재 검사하는 수를 A라고 했을때 벡터의 마지막 요소를 비교하여 

    - A 가 벡터의 마지막 요소보다 크면 벡터의 마지막에 추가해준다.

   - A 가 벡터의 마지막 요소보다 작으면 Lower bound하여 나온 index위치의 값과 교환해준다.

3. 최종적으로 만들어진 벡터의 길이 N이 최장 증가 수열의 길이가 된다.

그림으로 하나하나 표현하면 아래와 같습니다.

이렇게 최종적으로 만들어진 수열(0, 2, 4, 8, 9, 10)의 길이가 LIS의 길이가 됩니다.

문제의 정답인 잘라야 하는 전선의 수는 주어진 (n - LIS의 길이)를 하면 나오게 됩니다.

단 이 문제에서는 LIS의 요소를 요구하지는 않았는데 위에서 구해진 수열이 LIS를 나타내는건 아닙니다.

직접 눈으로 확인해봐도 수열 7    3    1    2    0    6    8    9    4    10 의 최장 증가 수열은 

1    2    6    8    9    10 이지만 LIS알고리즘을 통하여 구해진 수열은 0    2    4    8    9    10 입니다.

따라서 LIS의 요소까지 구하려면 추가적인 작업을 해야하지만 그 방법은 다음 문제에서 알아 보도록 하겠습니다.

전체 코드입니다.

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

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

문제 자체가 약간 난해한 면이 있지만 몇번 읽어보면 규칙을 파악 할 수 있을겁니다.

해를 표현하는 방법은 문제에 나와있는 그대로 <M:N> 이 주어졌을때 년도를 <X:Y>로 표현한다면 X,Y는 1,1로 시작해서 

1씩 증가하며 X>M이 되면 X%M, Y>N이 되면 Y%N을 해주면 됩니다. 

따라서 문제로 M,N,X,Y가 주어졌을때 <X,Y> 가 몇번째 해인지 알기 위해선 위의 조건을 적용시켜 1,1부터 시작하여 증가시키

며 검사하면 됩니다. 그러나 문제는 <X,Y>로 표현할 수 없는 해가 주어진다는 것인데 이 때 무한 반복을 하지 않으려면 처음

부터  반복의 끝을 정해주어야 합니다.

그리고 이 반복의 끝이 바로 문제에 나오는 '종말의 해' 인데 이 날을 구하는 방법은 바로 N과 M의 최소 공배수를 구하는 것입

니다. 이 N과 M의 최소공배수를 G라고 한다면 이 G번째 해가 달력의 마지막이기 때문에 첫번째 해부터 G번째 해까지 <X,Y>

로 표현되는 해가 없다면 <X,Y> 가 유효하지 않은 표현이고 따라서 -1을 출력해주면 되는겁니다.

최소 공배수를 구하는 방법은 유클리드 호제법을 이용하였습니다. 

최대 공약수 공식(gcd)

1. a,b: 최대 공약수를 구하고자 하는 두 수 

2. r: a를 b로 나눈 나머지 r=a%b

3. 식: gcd(a,b)=gcd(b,r) 을 b가 0이 될때까지 반복해주면 됩니다.

최소 공배수 공식(lcm)

1. a,b: 최소 공배수를 구하고자 하는 두 수

2. gcd(a,b): a,b의 최대 공약수

3 식: a*b/gcd(a,b)

전체 코드입니다.

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

정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 개 있다. 정보 초등학교에서는 학생들에게 이 방들을 배정하되, 배정된 모든 방에 빈 침대가 없도록 하고자 한다.

예를 들어, 방의 종류가 5인실, 9인실, 12인실이고 6학년 여학생 전체가 113명 이라면, 5인실 4개, 9인실 5개, 12인실 4개를 예약하면 각 방에 남는 침대 없이 배정이 가능하다. 또한 12인실은 사용하지 않고 5인실 10개와 9인실 7개만 사용하는 것도 가능하다. 그러나 방의 종류가 3인실, 6인실, 9인실이고 6학년 여학생 전체가 112명이라면 빈 침대 없이 방을 배정하는 것은 불가능하다.

방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오. 단, 세 종류의 방은 모두 충분한 개수가 있다고 가정하며, 위의 예에서와 같이 세 종류의 방을 모두 활용하지 않고 한 종류 또는 두 종류의 방만 이용하여 배정하는 것도 허용한다.

표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다.

빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다.

문제의 입력이 크지 않기 때문에 모든 경우O(n^3)를 탐색해도 시간안에 충분히 문제를 풀 수 있습니다.

따라서 재귀나 3중 포문을 이용하여 문제를 풀 수 있는데 저는 3중 포문을 이용하여 풀었습니다.

한가지 세 종류의 방을 전부 활용하지 않아도 된다는 점만 주의하면서 풀면 됩니다.

문제 출처: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으로 초기화 

시켜주면 됩니다. 

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

문제 출처: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번 나무에서 시작하는 경우를 각각 호출 해 주었습니다. 

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

전체 코드입니다.