Red Salmon

출처 : https://www.acmicpc.net/problem/10844

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/10844.cpp

정말 많은 생각을 하게 한 문제이다.

DP인것은 알았으나 어떤식으로 작성해야할지 정말 감이 오지 않았다.

역시 이럴땐 하나씩 다 해보는것이 최고이다.

나는 N이 1부터 3까지 전부 만들어 보았다. 시작값은 0이 될수없으므로 1부터 시작하여 

가장 앞자리가 1, 2, 3...9 까지 전부 구해보았다. (많은 DP문제가 이런식으로 접근한다.)

이렇게 하고나서 규칙을 찾기 위해 많은 시간을 소모했다. 

결국은 삼각형 구조였는데, 나는 삼각형구조를 생각은 했으나 직각삼각형 구조를 생각하여 쉽게 풀리지 않았던것 같다.

개인적인 경험으로 DP에서 이렇게 배열을 조합해야 한다면 결코 어렵게 풀리지 않으며, 특히 수가 나열된상태에서 찾는것이라면 상하좌우대각선포함해서 1칸씩 움직이는 범위안에 규칙이 존재하는것 같다.

뭐 결국은 풀어서 다행이다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/2565.cpp

이 문제는 초등부 올림피아드 문제이다. 심지어 거의 10년전에 출제된 문제인데... 난 이걸 최근에 알았는데... 

내가 왜 구직활동이 힘든지 이해가 된다. 전국에는 뛰어난 인재가 참 많은거 같다.

근데 뭐 나도 LIS를 사용하니 금방 풀긴 했다. 물론 LIS인지 빨리 파악하는게 매우 중요하다.

나는 다음과 같은 방법으로 접근했다.

1. 우선 겹치지 않아야 한다. 그러면 A를 기준으로 봤을때 B가 순차적이면 되면 될거같다.

2. A를 기준으로 입력을 정렬해보자. 그럼 예제는 다음과 같이 된다.

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

이렇게 보니 딱 사이즈가 나온다. 위에 3개를 쳐내면 4부터 최장증가수열이 만들어 진다.

즉, 나는 최장증가수열을 구하고 n에서 빼면 되는 것이다.

문제는 많이 어려워보이지만 실질적으로는 별거 없는 것이다.

출처 : https://www.acmicpc.net/problem/1965

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/1965.cpp

구직활동으로 거의 안풀었고 풀어도 올리지 않다가 이제 다시 블로그 작성 시작!

먼저 이 문제는 어떻게 봐도 다이나믹프로그래밍이라는것을 어필하고 있는 문제이다. 최대 개수를 구하라는 것은 완탐 or DP일텐데 만약 완탐으로 접근한다면 각 입력마다 최대값을 구하기 위해 선택을 하고 또 하는 과정이 있어야 할 것이고 TL을 피하기 위해선 메모이제이션이든 뭐든 미리 기록해놔야할것이다. 즉, 할수있을지 없을지도 미지수이고 굉장히 복잡해진다.

그러므로 간단히 DP를 써보도록 한다. 이 문제의 알고리즘은 LIS(Longest Increasing Subsequence)라는 알고리즘이다. 

이는 최장 증가 수열을 구하는 문제인데 예전에 캐쳐 미사일 문제를 풀때 공부해뒀던 것이다.

간단히 알고리즘을 적어보면 다음과 같은 과정을 밟게 된다.

1. 정답을 담을 배열을 만든 후 입력받은 배열의 한 요소씩 검사를 시작한다.

2. 만약 현재 정답배열의 사이즈가 0이거나 정답배열의 마지막 값보다 현재 검사하는 요소값이 크다면 새로이 추가를 한다.

3. 2번의 과정에 속하지 않는다면, 한칸씩 앞으로 이동하며 2번의 조건이 성립할때까지 인덱스를 탐색한다.

4. 그리고 최종적으로 배열의 크기를 출력하면 된다. 

이게 알고리즘의 전부인 굉장히 단순한 풀이이다. 예를 들면 다음과 같다.

예제를 보면 

1 6 2 5 7 3 5 6 인데

처음 1 6까진 증가수열이므로 그대로 두고 2가 들어오면

1 2 가 되며 6이 사라진다.

그리고 5 7까지는 그대로 다시 추가되어 1 2 5 7 이 구성된다.

그 후 3이 들어오게 되면 1 2 3 7 이 되고 순차적으로 5와 6이 추가되어 1 2 3 5 6

으로 최종 5가 출력되게 된다.

물론 이 풀이는 그닥 빠른 방법이 아니며 더 빠른 방법이 있다. 하지만 이 방법만 알아도 많은 문제를 풀 수 있으므로 알아두는게 좋다.

구현 방법은 사람마다 다를 것이기 때문에 굳이 나처럼 풀지 않아도 된다. 늘 강조하지만 알고리즘은 하나여도 풀이 방법은 수만가지가 나오는것이 프로그래밍이다.

출처 : https://www.acmicpc.net/problem/11057

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/11057.cpp

DP문제이다. 규칙을 찾는데 약 30분정도가 걸렸다. 좀 오래걸린거 같다. 

알고리즘은 다음과 같다.

1. 0~9까지 수별로 오르막수를 구해본다.

2. 자리수를 하나씩 높이면 그 직전수의 모든 합이 0번째 인덱스가 되고 그다음부터는 직전 녀석과 그 이전의 0번째부터 시작하는 배열값을 하나씩 매칭시켜 빼면 다시 수가 나오고 또 전체합을 통해 구한다.

3. 팁이라면 나는 0부터 차근차근 더해나갔는데 이러니까 10007 로 나눌때 상당히 까다롭다. 결국 난 해결하지 못했고 알고리즘을 수정했다. 수정한 알고리즘은 어차피 앞수가 9로시작하면 무조건 모든수가 999 이런식으로 진행되야 하므로 1개뿐이라는 사실을 알고 여기서 시작한다. 

여기서 시작하여 다시 똑같이 진행하면 9번째수에는 최종 합이 담기게 된다. 

이 문제는 알고리즘을 찾는것보다 이 나누는 경우를 어떻게 처리해야하나를 가지고 상당히 고민했던 문제이다.

결국 발상의 전환이었지만, 사람이란게 생각에 갖히기 시작하면 전환하기 참 힘든것 같다.