SLENDER ANKLES's 개발블로그

오래전에 풀어봤다가 포기한 문제였는데, 이번에 역시 어렵게 풀었다. 

n의 범위가 10000인 n * n 영역에서 (이미 배열을 잡을 수 없다는 것을 캐치)

l ( 4 <= l <= 100)길이의 그물을 쳐서

m(1 <= m <= 100)개의 물고기를 최대로 가져오게 할 때

그 물고기 어획량이 최대가 되는 마리 수를 계산하는 문제였다. 

그물은 우측으로, 아래쪽으로 칠 수 있다는 조건이 희망적이었다.

우선 대충 문제만 봐도 토가 나오는 문제였지만, 겁먹은 점도 많은 것 같다. 

이번에 느낀 문제 접근 방법은

[1] 규칙이 있나?

[2] 완전탐색 가능한가?

[3] 완전히 탐색하는데, 범위를 현저히 줄일 수 있는가?

이다. 

1번은 모르겠고, 2번은 안되었고, 3번의 방법을 적절히 선택해서 풀어야 하는 문제였다. 

맨 처음에는 문제 예시의 그림을 보고 

물고기 위치보다 그물을 쳐보면 되잖아? 개쉽네 이랬는데 

다음의 예외를 생각 못했었다. 

위와 같은 경우 물고기 좌표가 있지 않은 곳에서 그물을 쳐야 최대를 수확할 수 있다. 

그 다음 생각한 방법은 물고기의 입력 범위의 x, y의 최대 최소

4개의 값을 받아와서 

그 범위만큼 완전 탐색하는 것이었다. 

이 방법은 시간 초과가 났다. 

마지막 방법은 내가 완벽히 생각해내진 못 했다. 

이렇게 하는 것이다. 

 x좌표, y좌표를 각각 따로따로 sorting 한 후에 

그 좌표들을 이중 포문 돌리면서 탐색하니까 답이 나왔다. 

머리를 잘 굴려서 최대한 범위를 적게 하는 팁이 필요한 문제였다. 

실행 시간은 망이었지만..

어쨋든 꿀팁, x좌표, y좌표 정렬한 후에 완전탐색

느낀 점은 

*생각은 간단하고 명료하게 해야 된다. 

*너무 많은 조건으로 필요없이 시간을 허비하거나 코드 수를 늘릴 필요는 없다는 것이다.

우선 맵의 범위도 1~40000 (2차원 배열이기때문에 배열 선언하는 것은 불가)

목적지까지의 거리도 20억이 주어지므로 배열을 한칸씩 재귀적으로 탐색하는 방법은 절대 하면 안 되는 문제였다. 

그래서 예전에 풀어본 경험으로 한 번의 이동은 2차원 배열의 하나의 요소가 아니라 

벽에서 부터 ~ 벽까지 라는 것을 생각했다. 

다만 반복되는 루프를 만나면 계산을 좀 더 손쉽게 해줄려고 했는데, 사실 이 것은 별로 필요없었다. 

오히려 코딩시간과 디버깅의 시간을 더욱 잡아 먹었던 듯 하다. 

방향에 대한 처리가 중요한데, x축 진행 방향의 증가, 감소, y축 진행 방향의 증가 감소를 판별해

벽까지의 정확한 이동 경로와 거리를 측정해야 한다. 

우선 처음 진행방향은 x축 진행 방향도 +(증가), y축 진행 방향도 +(증가) 이다.

다음 벽까지의 거리가 더 가까운 축의 이동거리를 측정해서 

x, y모두 그 만큼 이동해주고, 이 과정을 반복한다. 

답이 잘 나온다. 

입력 좌표는  행 >> 열 >> 1행의 시작 열

이렇게 주어진다. 

그리고 좌표 정보가 주어지는 데 각 좌표는 로봇이 해당 좌표에서 어디로 이동할지에 대한 정보를 말한다. 

로봇이 밖으로 빠져나가면 빠져나갈때까지의 거리를 출력

로봇이 무한 루프에 빠지면 어디서부터 어디까지가 무한 루프인지 판단해서 출력하면 된다. 

1) 맨 처음에 초기화를 모든 좌표에 'a'를 것을 초기화해놓고, 입력을 받았으므로 n, s, w, e를 제외한

a로 진입하게 되면 빠져나간 것이라고 판단하여 답을 구했다. 

2) 무한 루프에 빠지는 것에 대해서는 visited배열을 놓고 이미 방문 한 곳으로 가면 루프를 도는 것이기 때문에 

그렇게 처리했다.

비교적 쉬운 문제

문제 이해가 제대로 안되 애를 먹은 문제다. 

카드 6장이 주어지면 카드 6장이 모두 베이비 긴 상태로 없어져야 한다. 

이 것을 이해하지 못해

처음에 베이비긴이 하나라도 있으면 되는 것인가? (X)

베이비긴을 만족하는 것이 2개 있으면 되는 것인가?(X)

베이비긴을 만족하는 것이 2개 이상 있으면 되는 것인가?(X)

모두 일정 테스트케이스에서 막혔다.

베이비 긴을 run상태 이든 트리플리트 상태이든

어쨋든 6장을 모두 써서 없애야 한다.

이 것이 문제에 핵심이었다. 

0~9까지의 배열을 가지고

각 입력 받은 숫자의 개수를 저장해놓았다. 

그리고 베이비긴을 만족시키는 연산을 통해 답을 도출해내었다. 

백트래킹 문제에 대해서 조금씩 감을 잡아가는 느낌이다.

이 문제는 완전 탐색을 하는 도중 첫 번째 답이 나오면 종료하는 것이 포인트다. 

나의 백트래킹 가지치기는 1부터 3으로 한 칸씩 늘려나가면서 만들어 가므로 

가장 먼저 나오는 첫 번째 답이 최소값이다. 그렇다면 더 이상 트래킹을 그만둬도 답을 도출해낼 수 있다. 

백트래킹에 대한 문제는 어느 정도 해소가 되었는데,

좋은 수열을 판별하는 방법이 의외로 까다로웠다.

처음에는 좋은 수를 판별하는 방법은 너무 복잡하고 까다롭고 분명 시간 소비를 많이 할 것 같아 

규칙을 찾아야 된다고 생각했는데, 그 것이 아니었다. 

좀 더 연구해보니까 분명 좋은 수열을 판별하는 것은 

인덱스 장난을 치는 부분이 조금 복잡하지만 절대 시간이 오래 걸리지는 않다는 것을 알았다. 

예를 들어 123123 이라는 수가 있으면

맨 끝의 인덱스부터 시작해서 length를 1부터 시작해서

length : 1

2-3 비교

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

length : 2

3 - 1

2 - 3

비교

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

length : 3

3 - 3 

2 - 2

1 - 1

비교 ===>(이 것은 나쁜 수열로 판별남)

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

이런식으로 판별했다. 

(현재의 점)을 기준으로 현재 점과 (현재의 점 - length)을 비교하는 과정을 통해

판별하는 것이다. 이 경우는 길이가 80이어도 40번만 수행 횟수는 정말 얼마 되지 않는다. 40번정도?

수를 완전탐색하면서 좋은 수열인지 판별하고 답이 나오면 최소값이므로 바로 종료하면 되는 문제였다.

<소스코드>