SLENDER ANKLES's 개발블로그

문제를 보고서 sort의 방법중에 최소시간이 걸리는 방법을 찾으라는 것인가?라고 생각했다.

퀵소트를 구현하는 것인가 했지만, 

2 3 5 4 1

=> 1 3 5 4 2

=> 1 3 2 4 5

=> 1 2 3 4 5

위와 예제를 보면 내가 생각했던 방법은 아니다... ???

** 시그를 통해 알게 된거 swap을 최소로 하는 것은 선택정렬 방법이다. ** 

우선은 선택정렬을 하는 방법으로 구현해 보고 안 되면 퀵소트라던지 힙소트라던지 구현해야 되겠다고 생각했다. 

내가 세운 방법은 이 것이다.

[]은 확정된 값들을 말한다.

2 3 5 4 1 중에 최소값을 첫 번째 배열에 넣는다.

=> 1 3 5 4 2

[1] 3 5 4 2 중에 최소값을 두 번째 배열에 넣는다.

=> [1] 2 5 4 3

[1] [2] 5 4 3 중에 최소값을 세번 째 배열에 넣는다.

=> [1] [2] [3] 4 5

.....

swap되는 카운트를 세는 것이 문제이기 때문에

간단한 조건을 하나 걸어주었다. 

최소값이 자기 자신이면 swap을 하지 않는다는 조건이다.

이렇게 하면 답이 나온다.

생각은 쉬운데 코딩하는게 까다로웠다?

생각도 물론 처음은 쉽지 않았다. 

1차원적인 생각으로 큰 사각형에서 작은 사각형을 빼서 답을 구해야겠다고 생각했다.

But, 어떻게 작은 사각형을 구하는지가 난감했다. 

조금 생각을 해보니, 둘레를 반시계방향으로 돈다는 조건을 통해서 작은 사각형을 구할 수 있었다. 

가장 긴 가로변, 가장 긴 세로변의 인덱스를 구한다.

둘 중에 나중에 나오는 변의 인덱스 + 2, 둘 중에 나중에 나오는 변의 인덱스 + 3 번

째의 변들을 곱해주면 작은 사각형을 구해 줄 수 있었다. 

다른 방법들이 많겠지만 나는 이 방법을 택했다. 

솔직히 이상적인 생각인지는 모르겠다. 몇 가지 예외를 처리해주어야 했다. 

1) 가장 긴 가로변인덱스와 가장 긴 세로변인덱스가 첫번째와 마지막인덱스에 배치되어있는 경우가 예외이다.

를 생각해야 한다. 말로 하기가 힘들지만 그림을 그리기는 너무 귀찮아서,,, 

이부분은 나중에 보더라도 이해해야 되는 부분 같다. 아무튼, 단지 인덱스의 크기만을 비교해서는 안된다는 것이다.

인덱스 크기만을 비교해서는 인덱스 크기가 더 큰 변이 우리가 구해줘야 하는 변 같지만 사실은 정반대라는 것이다.

조금 생각을 더 해야 된다는 것이다. 몇 번이고 답이 안 나왔는데 그래서 잘 못 풀었나 생각했는데

적어도 모양에 따라 2~3번 실제로 손으로 써보고 직접 코드를 따라 내려가면서 나의 잘못된 코드를 바로 잡았다. 

어쨋든 좋은 문제인거 같다. 까다로운 문제로서는

정답률이 그리 낮지 않은 문제인데 푸는데 정말 오래걸렸다. 

다른 프로젝트를 하고 있어서도 그랬지만 문제를 풀어가서 답을 구하는데 오랜시간이 걸렸다.

1. 우선 처음에 2차원 배열로 해야되나? 생각했는데 40000 * 40000이라서 이건 아닌거 같애서 이 방법은 넘겼다.

2. 개미의 진행방향과 시간을 인자로 가지는 재귀함수를 호출해서 구하면 어떨까?

=> 구현했더니 예제에 대한 답이 나왔다! 오호

3. But 시간 초과가 났습니다. ㅠㅠ 재귀함수 호출을 무지막지하게 해야 되는 방법이라는 것을 깨달았습니다.

4. 개미가 한 바퀴를 돌고 또 도는 동작이 있다는 걸 발견했습니다. 이렇게 되면 200000000이런식의 수행횟수를 돌아야 하더라도

재귀 호출 횟수를 엄청 줄여 줄 수 있다고 생각했습니다.

그래서 재귀함수 호출을 하는 소스를 사용하면서 위의 사이클을 발견해서 그 부분의 계산량을 줄여주었습니다.

그런데도 시간초과 ㅜㅜ 

시간 초과를 극복 할 수 있는 방법으로 문제를 풀어야 했지만 그에 마땅한 방법이 떠오르지 않아 고생하였다. 

그래서 백준 질문 게시판을 이용해서 약간의 해답을 얻고 답을 풀었다. 

5. 나는 이 문제를 일종의 배열을 한칸한칸 재귀적으로 나가는 방법을 사용했는데, 그 것이 함정이었다. 

x, y 좌표가 이동하는 할 때 벽을 부딪히는 것을 한 번의 재귀수행으로 풀어나가야 했던 것이다. 

간단히 말해 벽해 부딪힐 때까지 한 번에 진행하는 방식으로 문제를 풀어나갔더니 답이 나왔다. 

이렇게 벽을 부딪히는 것을 기준으로 재귀를 수행하게 되면 기존의 방법에 비해 훨씬 더 저렴히, 시간을 쓰면서 답을 해결해나갈 수 있게 된다. 이러한 방법을 생각해내지 못 했던 것이 안타까울 뿐..

물론 소스코드는 간단 명료 하진 않은데 이 부분은 답을 맞췄으니 다른 사람들의 코드를 참고하며 좀 더 보완해야 될 점이다. 

재귀 함수를 수행하는 부분을 간단히 설명하자면, 

void ant_movement(int x, int y, bool garostate, bool serostate, int movehour);

이런 구조를 갖는 재귀 함수를 설계했다. 

garostate와 serostate에 대해서 설명하자면

garostate는 x좌표가 오른쪽으로 이동 상태인지, 왼쪽으로 이동 상태인지를 나타낸다. 

serostate는 y좌표가 위쪽으로 이동 상태인지, 아래쪽으로 이동 상태인지를 나태낸다.

현재 좌표점에서 이동 방향중에 위 아래면을 먼저 부딪히게 되면, y좌표의 상태를 바꾸어주고

현재 좌표점에서 이동 방향중에 왼,오른쪽면을 먼저 부딪히게 되면, x좌표의 상태를 바꾸어준다.

이렇게 되면 재귀를 수행하게 되면서 문제에 제시된 특성을 가지면서 이동 할 수 있게 된다. 

이러한 코드를 작성하면서 간단명료하게 코드를 작성해주진 못 했지만 로직적으로는 문제 없는 코드를 만들어내었다. 

한 가지 더 고려해야 될 점은 

재귀를 수행하면서 다음 벽에 부딪히게 되기 전에 최종 시간이 되버리는 케이스가 있게 되는데 

예를 들어 재귀함수에서 수행하는 부분은 다음 벽까지 이동하는 것인데 다음 벽까지 이동하기 전에 답이 구해져야 된다. 마지막에 꼭 거치는 부분이다. 이 때는 (최종 목표 시간 - 현재까지의 이동 시간)으로 목표점의 좌표를 구할 수 있게 된다.  마지막 재귀를 마무리 하게 되는 basecase가 되는 것이다. 

설명이 길었지만 이런식으로 문제를 풀어나가게 되면 답을 구할 수 있게 된다. 

풀고 나니까 쉬웠지만 쉽게 풀지 못 한 문제였다. 

RGB거리 문제이다.

전형적인 DP문제라고 생각한다.

조건 1 RGB거리에 있는 집들은 빨강 , 초록, 파랑 색으로 칠해져야만 한다.

조건 2 이웃한 집과는 색깔이 달라야 한다.

가장 적은 돈으로 거리를 색칠 할 수 있게 할려고 할 때 그 비용은 얼마인가?

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

느낌은 전체의 경우의 수를 다 구해보는 것 인데 그렇게 해도 답을 나올 것 같다. 하지만

배열을 활용한 dynamic programming방법이 더 좋을 것 같아 이 방법을 토대로 답을 구하고자 한다. 

풀이 정리

1. 우선 입력 받은 각 집들의 RGB 비용들을 arr이라는 배열에 입력 받았다. 

문제에서 

3 26 40 83 49 60 57 13 89 99

과 같이 입력 받는다.

배열은 arr[집의개수][4]; 와 같이 설정하였따. 

RGB 세가지 색깔이지만 나는 배열을 0부터 접근하는 것보다 1부터 접근하는 것을 좋아하므로 2차원 배열을 4로 선언하였다. 

1, 2, 3이렇게 접근 할 생각이다.

배열의 1차원 인덱스에는 집의 번호를 말한다. 

배열의 2차원 인덱스는 3개로 구성되는데 R , G,  B 의 비용을 입력받는다.  

arr[1][1] = 26, arr[1][2] = 40, arr[1][3] = 83

arr[2][1] = 49, arr[2][2] = 60, arr[2][3] = 57

arr[3][1] = 13, arr[3][2] = 89, arr[3][3] = 99

와 같이 입력 될 것이다. 

2. 이렇게 입력 받은 것에서 최소비용을 구해야 하는 것이 이 문제의 핵심인데

dp[집의개수][4]라는 배열을 선언하였다.

우선 dp[1][1], dp[1][2], dp[1][3]에는 arr[1][1], arr[1][2], arr[1][3]의 값들은 그대로 넣는다. 

초기 값을 선언하는 것이다. (첫 번째 집까지는 자신의 값들이 최소비용이다)

두 번째 집부터 연산을 시작하게 된다. 

2번째 집에서의 특정 RGB값 + 앞쪽까지의 RGB의 최소값에서 자신과 다른 색의 조합에서의 최소값

이라는 점화식을 세워서 풀었다. 

위의 말이 무엇이냐면

2번째 집에서 Red를 택하면 

1번째 집까지의 Green Or Blue의 색상으로 선택된 최소값과 자신(Red)을 더하여 최소값을 구하는 것이다. 

2번째 집에서 Green을 택하면

1번째 집까지의 Red Or Blue의 색상으로 선택된 최소값과 자신(Green)을 더하여 최소값을 구하는 것이다.

..........

3번째 집에서 Red를 택하면

2번째 집까지의 Green Or Blue의 색상으로 선택된 최소값과 자신(Red)를 더하여 최소값을 구하는 것이다. 

점화식을 구하자면

dp[i][j] = (j를 제외한 dp[i - 1][k] 중에서 최소값 ) + arr[i][j]가 된다.

이런식으로 dp를 수행하므로써 그때그때마다 모든 경우의 수를 세는 것보다

메모이제이션(?)을 적용하여 빠른 연산을 할 수 있으며, 사실 더 복잡하지도 않은 것 같다. 

이렇게 이차원 배열을 이용해서 dp를 수행하는 것은 처음해보는 데 기본적인 문제이지만 많은 도움이 됐던 거 같다. 

1차원적으로 생각했다. 

돌게임에서 수근이 또는 창영이는 자신의 턴마다 1개 또는 3개를 가져 갈 수 있다고 했다. 

결국 어떠한 형태로 가져가든 간에 1개씩 가져가든 3개씩 가져가든, 홀수개만큼을 가져가는 것이기 때문에 누구의 턴에서 끝나는지는 사실 정해져 있다는 것을 깨달았다. 

나의 풀이 방법은 

(전체 돌의 개수 /  3) + (전체돌의개수 % 3)

와 같다. 이렇게 게임이 최종 몇 번안에 완료가 되는지를 구하고

그 완료된 게임의 횟수가 짝수이면 창영이가 승! 홀수이면 수근이가 승!이라고 판정했다.

// 풀고나서 생각해보았는데

어차피 전체 돌을 한 개씩 가져가면서 시행되는 게임의 횟수를 짝수인지 홀수인지 계산하면되므로 

전체돌의 개수 % 2 == 0  이면 창영 승

전체돌의 개수 % 2 == 1  이면 수근 승 

이렇게 판정하면 된다. 

우선 배열의 인덱스와 다른 형태의 입력 값을 받는 것을 고려해야 된다. 

방향만 바꾸어서 생각하면 된다.

문제는 달팽이 모양처럼 배열을 타고 들어가야 되는데 재귀적으로 풀어냈다. 

기본 포맷은 DFS에 착안했다. 물론 DFS는 아니다. 

기본 아이디어는 재귀적 함수 호출에 DIRECTION정보를 넘겨주며 DIRECTION방향으로 더이상 진행 할 수 없을 때 DIRECTION방향을 바꾸어주는 방법으로 문제를 해결해나갔다. 

어떤 의미인지 잘 이해가 안 갈 수도 있겠다. 

(1,1)에서 시작했을 때 

무조건 방향은 오른쪽방향 -> 아래방향 -> 왼쪽방향 -> 위쪽방향 으로 흐르게 되어있다.

그래서 방향을 int 형으로 만들어 생각했다.

right : 1, down : 2, left : 3, up : 4

그래서 현재 방향점에서 진행 가능하면 기존방향으로의 좌표를 증가시켜주면서 현재까지의 현재까지 진행된 순번번호를 함수의 인자로 넘겨서 답을 구하는 방식이다. 

다시 한 번 정리해서 올려야 겠다!