방앗간 개발자

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

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

전체 코드입니다.

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

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

위 그림은 출처에 있는 예제 입력을 그림으로 나타낸것인데 여기서 주의 하셔야 하는점은 그래프에 방향이 있는 방향 그래프 

란 것이고 입력에 대한 신뢰 관계를 이런식으로 표현해주어야 DFS, BFS연산을 수월하게 수행 할 수 있습니다.

위 그림에 대한 정답은 1,2번 노드가 각각 총 4개의 노드를 해킹 할 수 있기 때문에 1,2번 노드가 정답이 됩니다.

이제 문제를 풀어보자면 일단 그래프를 표현하는 것 부터 시작인데 그래프를 인접 행렬 그래프로 표현 한다면 문제의 n 값이 

최대 10,000이므로 2차원 배열 graph[10,000][10,000] 을 만들면 메모리 초과 오류가 나게됩니다. 따라서 그래프는 인접 리

리스트 그래프를 사용해야 됩니다.

인접 리스트로 그래프를 만들었다면 이제 모든 노드에 대해서 DFS, BFS연산을 수행하고 가장 많이 해킹 할 수 있는 노드를 찾

아서 오름차순으로 출력해주면 됩니다. 

저의 경우는 처음에 재귀를 이용한 DFS를 사용한다면 시간초과가 뜰거라 생각하고 큐를 이용한 BFS방법으로 문제를 풀었는

데 무엇이 잘못된건지 계속 시간초과를 받아서 결국 재귀를 이용한 DFS로 문제를 풀었습니다.