BOJ 13419 탕수육

문제 조건에 "같은 알파벳을 두 개 이상 포함하지 않는다" 라는 조건이 있다.
즉, 같은 알파벳이 나오지 않는다.
그리고 두 명이서 번갈아 하기 때문에, 숫자 2와 주어진 문자열의 길이의 최소 공배수를 구해서 먼저 시작하는 사람은 그 최소 공배수 길이만큼 문자열을 연결해놓은 상태에서 짝수 인덱스에 위치하는 단어를, 다음 사람은 홀수 인덱스에 위치하는 단어를 가져가는 식으로 풀었다.
문자열 길이가 짝수인 경우, 즉 2로 나누어 떨어지는 경우에는 두 명이 한 번씩 번갈아 가져가므로 그냥 홀수 인덱스, 짝수 인덱스로 나눠가진 후에 똑같이 반복되지만, 문자열의 길이가 홀수라면 반복되는 최소 단위인 홀수*2를 만든 후에 나눠가지면 된다. 똑같이 반복되는 최소 열이 된다.
만약 같은 알파벳이 나오지 않는다는 조건이 없었다면 이렇게 최소공배수를 이용해서 풀지 못했을 것이다.

참고 : 국민대학교 교내 대회 문제 풀이 슬라이드

BOJ 11058 크리보드

누를 수 있는 버튼이 4가지가 있는데,
1. A를 출력하는 버튼 (A)
2. 현재 화면의 A를 모두 선택하는 버튼 (Ctrl-A)
3. 선택한 내용을 버퍼에 복사하는 버튼 (Ctrl-C)
4. 버퍼에 있는 내용을 붙여넣는 버튼 (Ctrl-V)

그냥 간단히 말해서 키보드에서 A, Ctrl-A(전체 선택), Ctrl-C(복사), Ctrl-V(붙여 넣기) 이렇게 4가지 기능만 사용가능하다고 할 때, 이 4가지 기능 중에서 적절히 선택하여 N번 기능을 사용했을 때, 화면에 출력할 수 있는 A의 개수의 최대값을 구하는 문제이다.

무조건 1번 기능만 사용해서는 최대 N개인데, N이 작은 경우는 1번 기능만 사용하는 것이 A를 화면에 최대로 나오게 할 수 있겠지만, N이 일정 크기 이상일 경우에는 Ctrl-A, Ctrl-C, Ctrl-V 즉, 2, 3, 4를 반드시 사용해야 최대가 될 수 있다. 하지만 어떻게 써야 최대가 될지는 딱 감이 오는 것이 없다. 가능성 있는 모든 경우를 다 해봐야할 것 같다. dp로 접근해보자.

d[n]=버튼을 n번 눌러서 출력할 수 있는 A개수의 최대값....? 음 하지만 최대값으로 해버리면, d[n]이 최대가 되기 위해 d[n-1]이 최대값이 아니여야 할 수도 있기 때문에... 조건을 하나 더 넣어야 할 것 같다.
d[n][현재 버퍼에 있는 A의 개수?.... 음 어렵다.
한 번 다시 생각해보자.

d[n][bt] = n번째 버튼을 bt를 눌렀을 때, A개수의 최대값
d[n][bt] = MAX(nbt : 1~4, d[n+1][nbt]+(bt==1이면 +1, bt==4이면 버퍼에 있는 만큼..))
음... 이것으로는 부족하다. 버퍼에 얼마나 있는지도 알아야 한다. 생각해보자.
일단 최대가 되기 위함을 생각하면, 2. 전체 선택과 3. 복사 버튼은 항상 함께 써야한다.
2, 3을 썼다면 4. 붙여 넣기를 써야하는데, 4. 붙여 넣기 버튼은 쓸 때마다 버퍼에 있는 만큼 화면에 나오게 되고, 즉, 다음에 버퍼에 들어갈(2, 3을 눌러야 들어감) A의 개수가 (4. 붙여 넣기를 쓴 횟수 * 지금 버퍼에 있는 A의 개수 + 현재 화면에 있는 A의 개수)가 될 것이다.
그리고 2, 3을 한 번 쓸 때마다 그 것들이 버퍼에 복사되고... 그럼 현재 버퍼에 몇 개가 있는지도 기록해야하고 이 것은 메모이제이션이 되려나...음 안 될 것 같은...배열의 인덱스로 버퍼에 있는 것의 개수를 잡자니 n이 최대 100이라 수가 너무 커져서 불가능하다.

좀 더 간단하게 만들어 보자.
A를 출력하는 버튼은 1번 버튼 혹은 4번 버튼 뿐이다. 그리고 2, 3 버튼은 두 개가 항상 같이 쓰여야 한다고 볼 수 있다.
결국 버튼은 3개로 볼 수 있다. (1), (2, 3), (4)...
그리고 맨 처음에는 무조건 1번 버튼을 써야하고...

--------------------------------------------------------------------------------

음 도저히 생각이 안난다. 잠시 쉬다가 생각해보니, 현재 버퍼에 있는 것은 현재까지 출력되어 있는 것의 개수로도 볼 수가 있지 않나? 그렇다면 아예 d배열에 기록된 것을 사용하면 될 것이다. 아니다. 다시 생각해보니 현재까지 출력되어 있는 것의 개수를 (가장 최근까지 연속해서 사용한 4번 버튼의 개수)로 나눈 값이 버퍼에 있는 값이 될 것이다. 그렇다면
(가장 최근까지 연속된 4번 버튼의 개수)도 인자로 넣야할 것이다.
d[n][bt][con]=n번째 버튼 bt를 눌렀을 때, 그리고 n-1번째까지 가장 최근에 4번 버튼을 연속해서 con개 눌렀을 때, A개수의 최대값
d[n][bt][con]=MAX(nbt:1~4, con_pre는 nbt에 따라 con-1 or con,  
d[n-1][nbt][con_pre]+(bt==1이면 +1, bt==4이면 d[n-1][bt][con_pre]/con) )
그리고 답으로는 d[n][4][1~n]중 최대값을 구하면 될 것이다. 
                                                                                                   

다시 다시 다시...
결국 풀이를 보기로 했다. 내 힘으로 못 푼다는 것이 참 아쉽고 슬프지만, 그리고 여전히 dp를 무서워 한다는 것이 참 슬픈일이지만... 그냥 너무 아쉽다. 진짜 dp를 정복해보자. 1일 3dp가자...

일단 백준님의 풀이의 앞 부분을 보니
d[n]=크리보드를 n번 눌러서 화면에 출력된 A개수의 최대값
이라고 나와있다. 여기서부터 생각해보자.
근데 내가 처음 생각할 땐, 예를 들어 d[n]이 최대값이기 위해 d[n-1]은 최대값이 아니여야 할 수도 있어서 이것은 아닌 것 같다고 결론내렸는데... 풀이를 더 봐야겠다.

음 어느정도 이해했다. 확실히 와 닿지는 않지만...
d[n]에서 n이 작을 때는, 그냥 A만 누르는 것이 나을 수도 있지만, n이 어느정도 클 때, A의 개수가 최대가 되도록 하려면, 반드시 Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V...를 써야할 것이다.
이 때, Ctrl-V를 몇 번 쓰다가 Ctrl-A, Ctrl-C, Ctrl-V...를 써야할지는 해봐야한다.
그리고 Ctrl-V의 개수가 늘어남에 따라 Ctrl-A, Ctrl-C에서 버퍼에 저장된 개수도 비례해서 늘어난다. 

그래서 j를 (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, ..., 한 번 복사해서 붙여넣기를 하는 데 드는 횟수)라고 하면 d[n]=크리보드를 n번 눌러서 화면에 출력된 A개수의 최대값 이므로,
d[n]=MAX(d[n-1]+1, d[n-j]*(j-1) , j는 3이상 n-1이하 ) 이 된다.
d[n-1]+1은 마지막이 A누르는 것으로 끝나는 경우이다. (Ctrl-A, Ctrl-C를 누르는 데 2번은 걸리니까, n이 작을 때는 그냥A를 누르는 게 나은 경우가 있다.)
d[n-j]는 (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V,...)를 누르기 전까지의 상태를 의미한다. 즉, n-j번 눌러서 화면에 출력된 A개수의 최대값인데, d[n-j]에 j-1을 곱하는 이유는 뭘까?
n-j번 누른 이후, j번을 누르는데, 그 중 2번은 Ctrl-A, Ctrl-C를 누르는 데 사용된다. 그렇다면 Ctrl-V는 j-2번 누를 수 있는데, d[n-j]*(j-2)만큼 A의 개수가 증가하게 되고, 결국 원래 있던 d[n-j]와 합치면 d[n-j]*(j-1)이 되는 것이다.

내가 원래 처음에 d[n]=크리보드를 n번 눌러서 화면에 출력된 A개수의 최대값 <-에서 더 이상 나가지 못했던 이유가, d[n]이 최대값이 되려면, d[n-1]같이 d[n]전에 있는 값들은 최대값을 가지면 안되는데... 하고 걱정했었다. 하지만, d[n]을 구하는 데 필요한 값들을 아무거나 갖다 쓰는게 아니라, (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V,...) 단위로 끊어서 보기 때문에 괜찮다. 예를 들어, (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V...)에서 중간에 Ctrl_A지점에서 끊어버리면 내가 위에서 걱정했던 문제가 발생할 수 있다. Ctrl-A로 끝나느니, 그 이전의 Ctrl-V를 한 번 더 하고 끝나는 게 낫기 때문이다. 하지만 저렇게 (Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, ...) 단위로 끊어서 모든 경우를 다 해보면서 그런 문제는 생각하지 않아도 된다.

이렇게 쓰다보니 그래도 어느정도 이해가 되는데, 아직도 100%라고는 못하겠다.
열심히 하자.

출처 : 백준님 강의 자료 풀이

BOJ 13415 정렬 게임

입력으로 수열이 주어지고, 그 수열을 정렬할 것인데, 어떻게 정렬할 것이냐면
k개의 (a, b)로 구성된 세트가 입력으로 들어오는데, 한 세트(a, b)는 수열의 1번 수부터 a번 수까지 오름차순으로 정렬하고 수열의 1번 수부터 b번 수까지 내림차순으로 정렬하는 것을 의미한다.
이렇게 k번의 세트에 대해서 모두 정렬이 끝났을 때의 수열을 구하는 문제이다.

수열의 길이가 최대 10만, k값도 최대 10만이라 일일이 다 정렬하다가는 시간초과가 날 것이다. 좀 어려운데, 생각하다 보니 조건에 특이한 점이 있다. 바로 항상 1번 수부터 정렬하는 것이다. 오름차순이든 내림차순이든 주어진 세트(a, b)만큼 정렬하려면 무조건 수열의 처음부터 정렬해야 한다. 그리고 한 세트당 오름차순 정렬을 내림차순 정렬보다 먼저하게 되므로, a<=b인 경우는 오름차순 정렬이 의미가 없다. 그리고 항상 처음부터 정렬하기 때문에, 앞에서 어떻게 정렬했든 간에 앞에서보다 더 큰 값이 나오면 앞에서 정렬한 것이 의미가 없다.

이런 특성을 가지고 잘 생각해보면, 일단 들어오는 k개의 세트(a, b)를 보면서 a<=b인 경우는 b값만 생각하면되고, a>b인 경우는 a, b값 모두 주의깊게 봐야한다. 그리고 a값, b값에 대해서 최대값이 의미가 있으므로 최대값을 구한다. 최대값이 맨 앞에 나온 경우에도 의미가 있는 것이, 예를 들어 가장 큰 값으로 내림차순으로 1~10까지 정렬하고, 그 이후에 더 두번째로 큰 값 1~7까지 오름차순 정렬이 나왔다고 하면 일단 처음에 정렬해놓은 것 중 8~10은 내림차순으로 결정이 되고 바뀌지 않는다. 그렇기 때문에 최대값을 구해서 최대값만큼 정렬을 해놓고... 그 다음으로 큰 값에 대해서 체크해주는 식으로 나가면 될 것 같다.

그럼 k개의 세트(a, b)값들을 입력 받으면서
a<=b인 경우는 b값만 받고 내림차순이란 것과 들어온 순서를 기록하고
a>b인 경우는 a값-오름차순, b값-내림차순, 및 들어온 순서 정보를 기록하는 식으로 받아서
내림차순으로 정렬(1. 값의 크기 기준, 2. 들어온 순서-나중에 온 것이 우선)한 후, 차례로 보면서 배열에 분배하면 될 것 같다.
분배할 땐 미리 원래 수열을 최대값까지 오름차순으로 정렬해놓고, ***
내림차순으로 정렬해놓은 세트값들을 최대값부터 보는데, 가장 나중에 들어온 최대값 이후부터 봐야하므로, 최대값의 들어온 순서이상(더 늦게 들어온)인 것들만 본다. 그리고 또 계속해서 들어온 순서보다 늦게 들어온 것만 봐야한다. 점점 값이 작은 것이 들어올텐데, 앞에 온 것들은 의미 없기 때문이다!!
내림차순 부분이면 다음 오름차순 부분이 오기 전까지 정렬된 수열의 작은 값부터 채워넣고,
오름차순 부분이면 다음 내림차순 부분이 오기 전까지 정렬된 수열의 큰 값부터 채워넣는다.

겨우 겨우 생각했는데, 아직도 헷갈린다. 구현해 봐야겠다.
코드가 너무 지저분해졌다... 그리고 예제만 만족시키고 제출했더니 시간초과가 나서 테스트 케이스를 돌려보는데 무한루프... 계속 고쳐봤는데... 모르겠다. 애초에 구현도 어렵고 코드도 너무 지저분하다. 풀이를 봐야겠다.
------------------------------------------------------------------------------
풀이를 보니 스택을 이용해서 하는 것으로 되어있다... 아... 왜 스택을 전혀 생각 못했을까...생각해 봐야겠다.
생각해보니 스택을 사용하면 위에서 내가 생각했던 것을 훨씬 쉽게 구현할 수 있다.
a<=b인 경우는 b값만 스택에 넣고, a>b인 경우는 a넣고 b넣되, 값을 넣을 때는 스택에 들어 있는 값이 먼저 나온 세트이므로 자기보다 큰지 확인하고 넣어야 한다. 같거나 더 작다면 스택이 비거나 자신보다 더 큰 값이 나올 때까지 빼고 넣는다. 그리고 더 크더라도 방향(오름차순인지 내림차순인지)이 같다면 넣지 않아도 된다. 이런 식으로 채워넣으면 가장 큰 값부터 작은 값순으로 오름차순, 내림차순,...이렇게 방향도 번갈아 스택에 쌓이게 된다.
그리고 내가 위에서 했던 것처럼 구현하려면 스택의 맨 아래값부터 사용해야 하므로 스택을 하나 더 만들어서 옮긴 후 스택의 위에서부터 하나씩 사용하면 된다. 스택의 위에서 뺀 값부터 시작해서 다음값까지 미리 정렬해 둔(가장 큰 세트의 값만큼만) 수열에서 빼서 채워주면 될 것이다.
구현해보자. 확실히 스택을 쓰니까 훨씬 쉽게 구현할 수 있는 것 같다...
내가 구현에서 좀 실수해서 고치고 다시 내서 겨우 AC를 받았다.
참 좋은 문제이다. 스택이라는 자료구조를 이용한느 것도 중요하지만 그 전에 정렬하는 규칙의 핵심을, 원리를 잘 파악하는 것이 매우 중요하다. 스택에 들어있는 값을 이용해서 정답을 구해내는 부분을 위해 생각을 많이 해야한다.
결국 내 힘으로는 못풀었지만... 많이 배운 문제였다. 꼭 나중에 다시 풀자.

BOJ 13997 구간 나누기 2

n개의 수로 이루어진 수열이 주어지면, m개 이하의 그룹으로 묶는데 각 그룹은 1개 이상의 연속된 수들로 이루어져야 하고 수열의 모든 수가 그룹에 포함되어야 한다.
이 때, 각 그룹에서 최대값과 최소값의 차이가 구간의 점수인데, 각 구간의 점수들 중 최대값이 최소가 나오도록 모든 수를 다 포함하는 m개 이하의 그룹을 만들어야 하는 문제이다.
그래서 최대값 중 최소인 값을 구하는 문제이다.

일단 m개 이하의 그룹을 만들라고 되어있는데, m개 이하의 그룹으로 최대값이 최소가 된다면 m개의 그룹으로도 최대값이 최소가 될 것이다. 그러니까 그냥 m개의 그룹을 만든다고 생각하는 게 편할 것 같다.

어렵다. 하지만 정말 감사하게도 아이디어가 하나 떠올랐다.
일단 주어지는 수는 1이상 10000이하의 수들이다. 그렇다면 그룹을 만들었을 때 차이의 값으로 나올 수 있는 값은 0 ~ 9999 일 것이다. 일단 m개 이하의 그룹으로 모든 수를 묶긴해야 하는데, 직접 그룹으로 묶어본다. 어떻게 묶을 것이냐면, 일단 m개 이하의 그룹으로 만들어야 하는데, 앞에서 얼마나 묶느냐에 따라 m개를 넘어갈 수 있는데, 일단 묶을 때 개수를 최소로 되게 해야하므로 묶을 수 있는 한 최대한 많이 묶어준다. 그래야 m개 이하가 될 가능성이 커진다. 근데 묶을 때 무엇을 기준으로 최대한 많이 묶으란 말인가? 바로 그룹내의 차이값을 정해놓고 그 이하가 될 수 있는 수들은 최대한 많이 묶는 것이다. 그렇게 묶어서 그룹이 m개이하가 되면 차이값을 더 줄여서 해본다. 차이는 0~9999이고, 그룹을 묶는데는 O(N)이 걸리므로 시간 내에 충분히 들어올 수 있을 것이다.

하지만 일정한 차이값 이하를 유지하면서 그룹을 묶는 것도 문제이다. 그럼 각 그룹에서 최대값, 최소값을 기록해가면서 묶어야 하나? 그러면 될 것 같다. 아니면 정렬을 해서, 작은 값부터 그룹을 묶는 시작점으로 놓고 묶기 시작하는 것도 편할 것 같다.

그리고 모든 차이값(0 ~ 9999)에 대해 다 해볼 것이 아니라 이분 탐색으로 해보는 것이 훨씬 빠를 것이다.

구현해 봐야겠다. 구현하니 예제는 제대로 나오는데 구현이 생각보다 간단치는 않았다. 정렬후 작은 값부터 묶는 방식으로 했는데, 순서상 첫 번째 수 부터 시작하면서 각 그룹에서 최대값, 최소값을 기록해 가면서 묶는 방식으로도 구현해 봐야겠다. 구현 자체는 각 그룹에서 최대, 최소값을 기록해 가면서 묶는 방식이 더 쉬운 것 같다. 두 코드 모두 제출해서 AC를 받았다! 아... 좀 무기력해 있었는데 어떻게 풀어야할지 생각이 나다니...감사합니다. 열심히 해야겠다!

BOJ 2192 두 수열

길이가 각각 N, M인 두 개의 수열 A, B가 주어지는데 (수열의 수는 양의 정수로 이루어짐),
수열 A의 뒤에서부터 k1개의 합을 S1이라고 하고, 수열 B의 뒤에서부터 k2개의 합을 S2라고 하자. 각각 k1, k2개를 선택했을 때, (S1-k1)*(S2-k2) 값이 그 단계에서의 점수가 되고, 선택한 k1, k2개의 수열을 제거하고, 남은 수열에서 같은 방식으로 진행하고, 두 수열을 이루는 수들이 모두 제거되었을 때까지의 각 단계별 점수의 합의 최소값을 구하는 문제이다.

BOJ 3114 사과와 바나나

R*C개의 칸으로 이루어진 영토가 있고 각 칸에는 사과 나무 또는 바나나 나무가 1개 이상 99개 이하 심어져 있다. 영토를 나누는데, 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래로 이동하면서 경계를 만들고, 그 경계 아래의 사과나무 개수와 경계 위의 바나나 나무 개수의 합이 최대가 되도록 하려고 한다. 경계를 만들며 이동할 때는 오른쪽, 아래쪽, 오른쪽-아래 대각선 이렇게 3가지 방향으로만 이동할 수 있고, 맨 오른쪽 아래칸까지 가야한다. 그리고 경계를 구성하는 칸의 나무의 수는 포함시키지 않는다.

다이나믹 프로그래밍이다. 처음에는 숨이 턱 막히는... 것 까지는 아녀도 거부감이 확 들었는데, 언제까지 이럴 것인가 이제 내 힘으로 풀 수 있는 문제도 좀 생겼고, 몰라도 풀이보면 웬만해서는 다 이해할 수 있지 않은가.. 즐기자 즐기자 즐기자!
 맨 왼쪽 위에서부터 시작해서 세가지 방향으로 이동하는 것을 dfs로 구현하면서... dfs+dp를 쓰면 될 것 같다. dfs + dp는 좋은데 문제는 이동하면서 아래, 위의 사과, 바나나 개수는 어떻게 알 것인가 이다.
바로 미리 각 행별로 0열부터 n열까지의 사과 나무의 개수, 바나나 나무의 개수 부분합을 각각 구해놓으면 된다. 그리고 경계를 만들면 경계를 구성하는 칸까지의 각 나무의 개수를 행 별로 얻을 수 있고 그 값들을 합하면 된다. 물론 간단하지는 않을 것이다. 대각선으로 이동하거나 아래로 이동한 경우는 간단한데, 오른쪽으로 이동했다면 같은 행이므로 조금 신경을 써야할 것이다.

그리고 d[r][c]= (r,c)를 경계의 한 칸으로 정했을 때, 경계 아래이 사과 나무, 경계 위의 바나나 나무의 개수의 합의 최대값
으로 놓으면
d[R][C] = MAX(nextR, nextC는 (R,C)로 부터 3가지 방향,
               d[nextR][nextC]+psumA[R][C-1]+psumB[R][n]-psum[C] )
일텐데, 물론 오른쪽으로 이동한 경우는 psumA, psumB를 더하는 부분에서 좀 조건을 더 넣어주든가 해야할 것이다.

일단 구현해보자!
구현하다가 문제였던 것이, 오른쪽으로 이동하는 경우인데, 만약 계속 오른쪽으로 가게 된다면 언제부터 오른쪽으로 온 것인지를... 즉, 자신의 왼쪽에 몇 개가 있는지를 알아야할 것 같았다. 그래야 그만큼을 계산안하거나 빼거나... 음 그렇다면 d[R][C][X]이렇게 3차원 배열로? 그럼 1500*1500*1500 으로... 메모리 초과가 분명해 보인다.
하지만 감사하게도 더 고민하다보니 처리할 수 있는 방법이 생각났다. 직전값이 바로 왼쪽값이면(즉, 오른쪽으로 이동한 것이라면) 직전값에서 계산했던 값에서 현재 위치의 값을 빼주기만 하면 되는 것이다. 구현해 봐야겠다.
내 구현 방식은 현재 위치에서 다음 위치로 넘어가는 것이라 아예 현재 위치에서 아무것도 더하지 않고 현재위치 값을 빼는 식으로 구현해야할 것 같다.

그리고 하나 더 예제가 안 나와서 알아봤더니, 처음에 psumA와 psumB를 구할 때, 'A'이면 psumA를 'B'이면 psumB를 계산했는데, 이렇게 하면 중간 중간 빈 공간이 생긴다. 0으로 초기화 되어있는 공간이 생긴다. 그래서 psumA는 'B'가 들어올 때는 직전값을 대입해주고, psumB는 'A'가 들어올 때 직전값을 대입해주는 연산도 추가해야 한다! 기본 중 기본이다 이건!

음 틀려서 살펴보던 중에 기저 사례를 처리하는 부분에서 맨 오른쪽 아래(R, C)에 도착했을 경우 마지막 행의 값을 return해주는데, 만약 맨 오른쪽 아래에 도착하지 않는 경우에는 어떻게 해야할지 고민하다가 그냥 NEGINF= -20억을 return하도록 ret=-2e9로 초기화 해놨다.
그런데도 틀려서 고민중이다...예제를 만들어 보던 중... 아 감사하게도 깨달았다.
감사합니다. 입력을 받을 때 숫자가 한 자리만 들어온다고 생각하고 %1d로 받고 있었다...
최대 99까지 들어오니까 그냥 %d로 받아야한다!!

그래도 틀렸다! 하지만 이번에는 또 찾아냈다. 정말로... 엄청난 실수를 했다.
오른쪽으로 이동하는 경우를 처리해주는 데서 실수했는데, 현재 위치에서 다음 위치로 넘어갈 때, 다음 위치부터의 최대값에서 현재 위치의 값을 빼주는 식으로 구현할 때, 다음 위치에서 계산한 값은 경계선이 되는 칸 왼쪽의 A의값의 합, 그리고 오른쪽의 B의 값의 합이다.
그런데 만약 현재 위치값이 B의 값이 존재한다면, 빼줄 필요가 없는 것이다! 빼면 안된다! 왜냐하면 아예 경계가 되는 칸 왼쪽의 B값은 계산하지 않았기 때문에! ...나는 여태 A값, B값을 다 뺐었는데, A값만 빼주면 된다!!!
고쳐서 제출해 봐야겠다. 와 AC를 받았다!

음 그렇게 어려운 문제는 아니겠지만 적어도 나에게는 좀 어렵고, 내 실수를 유도하는(?) 그런 문제였다. 

백준님의 풀이를 봤는데, 비슷하지만 조금 더 이해하기 쉽고 좋아보이는 방법이 있었다. 부분합을 구해놓되, 사과 나무의 부분합은 행별로, 바나나의 부분합은 열별로 구해놓고, 오른쪽으로 가는 경우에는 다음 칸에 해당하는 열의 바나나의 부분합만 더해주면 되고, 대각선으로 갈 때는, 다음 칸의 행, 열에 해당하는 사과와 바나나의 부분합을 다 더해주면 되고, 아래로 갈 때는, 다음 칸의 행에 해당하는 사과의 부분합만 더해주면 된다.

나중에 이 방법으로도 풀어봐야겠다.

BOJ 1514 자물쇠

디스크 N개로 구성된 자물쇠가 있다. 각 디스크에는 숫자가 0부터 9까지 디스크의 각 칸에 차례로 적혀있고, 9다음의 수는 0이 온다(즉, 원형의 디스크에서 0과 9가 인접해있다.).
자물쇠의 디스크를 돌릴 때, 시계 방향 또는 반시계 방향으로 최대 3칸까지 돌릴 수 있고, 한 번에 최대 3개의 인접한 디스크를 동시에 (시계 방향 또는 반시계 방향으로 최대 3칸까지) 도릴 수 있다.
이 때 N자리의 현재 자물쇠 상태가 주어지고, N자리의 비밀번호가 주어지면, 현재 상태에서 비밀번호를 맞추기 위해 자물쇠를 최소 몇 번 돌려야 하는지 구하는 문제이다.

자물쇠의 첫 디스크 부터 시작해서 각 디스크 마다 인접한 몇 개의 디스크를 1칸, 2칸, 3칸 씩 돌려보는 경우로 다 해봐야겠다고 생각했는데, 질문 게시판 질문과 답변 을 보니 그게 아니었다.


1개 1칸, 인접한 2개 1칸, 인접한 3개 1칸 이렇게 돌리는 경우가 최소일 수 있다.
예를 들어 123 -> 444로 바꾸려면 위와 같이 돌려야 최소 횟수인 3번이 나온다. 그런데 이 것은 디스크 1에서 모두 돌린다는 것을 의미한다.
 하지만 나는 처음에 이 것을 디스크 1에서 1칸 돌리고, 디스크 2에서 디스크 2, 1을 묶어서 1칸 돌리고, 디스크 3에서 디스크 3, 2, 1을 묶어서 1칸 돌리면 된다는 식으로 생각했는데, 결국 디스크 1에서 3가지 경우를 다 돌리는 것이나 디스크1, 2, 3에서 각각 한 가지 경우씩 돌리는 것이나 결과는 같지만 dp 배열의 정의를 세우려할 때, 내가 생각한 방법은 멘붕을 겪게 된다...

만약 내가 생각한대로 한다면, 디스크 2에서 돌릴 때와 디스크 3에서 돌릴 때 경우의 수도 많아지지만, 직전 값이, 과거에 계산했던 값이 변하게 될 수 있다. 위의 예대로라면, 디스크3을 돌릴 때, 디스크 1, 2, 값이 변하게 된다. 그럼 그 변한 값이 목표로 하는 비밀번호 값이랑 같은지도 검사해야하고, 이미 비밀번호 값과 같게 해놨다면 변경되면 안되고... 복잡해진다.

디스크 3을 돌릴 때, 디스크 1, 2값은 영향 받지 않으면 편하지 않을까? 디스크 3을 어떻게 돌리든, 디스크 1, 2값은 영향 받지않고 확정돼 있다면 디스크 1, 2를 돌리면서 비밀번호의 디스크 1, 2 값과 같게 해놓고 디스크 3만 신경 쓰면된다. 이렇게 디스크를 하나씩 확정해나가면서 모든 경우를 다 보는 것이 훨씬 편하다.

근데, 디스크 3을 어떻게 돌리든 디스크 1, 2를 신경쓰지 않으려면 디스크 3과 인접한 디스크를 돌릴 때, 디스크 4, 5만 포함해서 돌려야 한다. 즉 디스크1, 2를 동시에 혹은 1, 2, 3을 동시에 돌리는 것은 디스크 1에서만 할 수 있고 디스크 2, 3을 돌리는 것은 디스크 2에서만 할 수 있는 식이다.
그런데 이렇게 하면 정말 모든 경우를 볼 수 있을까? 하는 생각이 들었다.
디스크 3을 돌릴 차례에도 디스크 1, 2를 같이 포함해서 돌려야하지 않을까? 아니다. 왜냐하면 디스크 3에서 인접한 디스크 2와 함께, 즉 디스크2, 3을 돌리는 것이나 디스크 2에서 디스크 2, 3을 돌리는 것이나 효과는 똑같다. 미리 하고 나중에 하고의 차이다. 디스크3에서 디스크 2, 3을 추가로 돌리는 것은 디스크 2에서 디스크 2, 3을 그만큼 미리 더 돌리는 것이나 똑같기 때문에 이렇게 하면 모든 경우를 볼 수 있다.

그리고 헷갈릴 수 있는 것이 돌릴 수 있는 칸의 수가 한 번에 최대 3칸이라고 했는데, 한 번에 3칸이므로 예를들어, 5칸은 못 돌리는 게 아니라, 5칸을 돌리고 싶다면 두 번만에 돌리면 된다.

자, 이제 이해를 했으니 식을 세워보자.
d[n][a][b] : n번 디스크를 비밀번호에 맞추기 위해 돌릴 것이고, n번째(현재) 디스크가 a칸 만큼 돌고, n+1번째 디스크가 b칸 만큼 돌아 있는 상태일 때, 비밀번호로 맞추기 위한 최소 횟수. 답은 d[1][~][~] 중 최소값을 찾으면 될 것이다.-> d[0][0][0]을 구하면 될 것 같다. before[0]==after[0]으로 같고 최소값을 구하는 것이므로 d[0][0][0]을 구하면 d[1][~][~]중 최소값이 구해질 것이다.
식은 d[n][a][b] = MIN( d[n+1][na][nb] + (n번 디스크를 돌린 횟수) ) 가 될 것인데, n번 디스크를 비밀번호에 맞추기 위한 모든 가능한 경우를 다 해봐야하기 때문에 간단하지 않다. 일단 구현을 해봐야 겠다.

d[100][10][10]으로 선언하려고 한다. 왜냐하면, n번째 디스크를 돌릴 때, n번째 디스크는 최대 9번까지 돌려야 한다. 10번을 돌리면 제자리이기 때문에 안 돌리는 것이 낫다. 혹시 10번을 돌리면서 n+1, n+2번째도 같이 돌아가면 최소의 경우가 나오지 않을까 하는 생각을 할 수도 있는데, 전혀 그럴 필요가 없는 것이 n번째 디스크는 가만히 놔두고, n+1번째 디스크 차례가 오면 그 때 돌려버리면 되기 때문이다.

모든 가능한 경우를 해보는 것을 구현하려 하는데, 생각해보니 n번째를 양수만큼(시계방향) 돌릴 것이면 n번째와 인접한 n+1, n+2를 돌릴 때도 양수만큼 돌리면 된다.(음수만큼 돌리는 경우는 해 볼 필요 없다) n번째를 음수만큼 돌릴 것이라면 당연히 나머지도 음수 만큼 돌리면 된다.. 왜냐하면 n번째를 양수만큼 돌리고 인접한 n+1과 n번째를 음수만큼 돌리는 것은 n번째를 그만큼 덜 돌리거나 혹은 음수만큼 돌리거나.. 혹시 필요하다 해도 n+1번째를 볼 때, 음수로 돌려버리면 된다 그러면 결국 횟수는 같다.
그러니까 최소가 나올 가능성이 있는 모든 경우를 보되 최소가 나올 수 없는 경우나 안 봐도 되는 경우는 보지말자는 것이다.
그래서 일단, 시계 방향으로만 돌리는 경우, 반시계 방향으로만 돌리는 경우로 보려고 한다.

구현을 했는데, 몇가지 안되는 경우가 있어서 고민하다가 잘못한 부분을 발견했다. 바로 n번째에서 돌리는 경우, n번째 i번, n+1번째까지 j번, n+2번째까지 k번 돌리기 때문에
n번째는 i+j+k번 돌아가고 n+1번째는 j+k번 돌아가는데, n+1번째가 j+k번 돌아간다는 것을 깜박했다... 일단 그걸 고치니 맞게 나오는데, 제출해 봐야겠다.

와 맞았다!! 다른 사람들에 비해 시간이 좀 더 걸리긴 하지만... 일단 백준님 풀이와, 다른 사람들 풀이 등을 확인해보고 비교해 봐야겠다.

백준님의 코드를 보니, 음수만큼 돌리는 부분을 나처럼 따로 for문으로 처리한 것이 아니라, 양수만큼 돌리는 부분에서 처리하신 것 같다. 좀 더 정확히 말하면 양수만큼 돌리되, 어떻게 돌리든 최소 횟수로 돌리게 처리하셨다. 무슨 말이냐하면 예를 들어 0에서 7으로 돌리려면 7만큼 돌려야 해서 미리 초기화 해놓은 num[7]==3 으로 3번 돌려야한다는 것을 알 수 있는데, 사실은 그렇지 않다. 0에서 음수방향으로 가면 7까지 가는데 3칸만큼 돌려야 해서 1번만 도리면 된다. 그래서 백준님은 num[7]==3이 아닌 num[7]==1로 초기화 해놓으셨다. 그럼 양수만큼 돌리는 경우만 for문으로 해봐도 항상 최소 횟수로 돌리는 경우를 택하게 된다.

그리고 나는 인접한 1개, 2개, 3개를 돌리는 경우를 다 for문으로 해봤는데, 백준님은 인접한 2, 3개만 for문으로 모든 경우를 다 해보시고 1개만 돌리는 경우는 2, 3개를 돌리는 경우에 맞춰서 바로 결정하신다. 2개, 3개를 돌리는 경우는 다른 디스크에 영향을 주기 때문에 모든 경우를 다 해보고 1개만 돌리는 것은 다른 디스크에 영향을 주지 않기 때문에 2개, 3개를 돌린 경우에 따라 목표 번호에 맞게 맞추면 되는 것이다.

지금 다시 짜보면서 깨달은 것은
d[n][a][b]의 의미이다. n번째를 돌릴 것이고, n-1까지의 돌림에 의해서 n번째가 a번, n+1번째가 b번돌아 간 경우 비밀번호로 맞추기 위한 최소 횟수!

참조 : 질문 게시판 질문과 답변 ,백준님 강의 자료 풀이 참조