Description

• 본 문제는 그리디로 풀 수 있다.
• 한 곡괭이로 캘 수 있는 5번 횟수에 대해 각 구간을 정한다.
  • 모든 미네랄에 대해 곡괭이로 캘 수 있는 횟수까지 대해 구간을 정한다.
    • 곡괭이 1개라면, 5회, 2개라면 10회, …
  • 이 때 곡괭이로 캘 수 있는 수량 보다 미네랄이 적을 수 있으므로, 내가 볼 구간의 length는
    • Math.min( 곡괭이 횟수, 광물 수 / 5 )
      • / 5를 해주는 이유는 한 곡괭이로 5번 밖에 못 캐기 때문이다.
  • 이에 대해 모든 곡괭이를 사용하여 얼마만큼의 비용이 발생하는지 확인한다.
    • 곡괭이가 없어도 일단 계산한다. 나중에 조건을 이용해 사용하지 않으면 되기 때문
• 각 구간에 대해 값을 모두 구했다면, 이를 돌 곡괭이 > 철 곡괭이 > 다이아몬드 곡괭이 순으로 우선순위 큐에 삽입한다.
  • 돌 곡괭이로 많은 비용이 발생했다면, 이는 광물이 비싸다는 뜻이고, 따라서 더 좋은 곡괭이로 캘 수록 효율이 높아지기 때문.
  • 철 곡괭이도 마찬가지
• 이 후 우선순위 큐 에서 하나씩 꺼내면서 가지고 있는 제일 좋은 곡괭이로 캤을 때 발생하는 비용을 추가하면 정답
  • 이 때 이미 비용은 계산해 놓았기 때문에, 해당 구간에서 해당 곡괭이 값을 찾으면 된다.

Result

import java.util.*;
class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int picksCount = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            if(o2[2] != 0 || o1[2] != 0)
                return o2[2] - o1[2];
            if(o2[1] != 0 || o1[1] != 0)
                return o2[1] - o1[1];
            return o2[0] - o1[0];
        });
        
        for(int i = 0; i < picks.length; i++)   picksCount += picks[i];
        
        //* 좋은 곡괭이로 캘 수록 피로도는 적어진다.
        //* 좋은 곡괭이로 좋은 광물을 캘 수록 피로도는 적다.
        
        //* 다이아몬드가 많을 때 다이아로 캐는게 좋다.
        //* 철이 많을 때 철로 캐는게 좋다.
        //* 돌이 많을 때 돌로 캐는게 좋다.
        //* 한 번에 5개씩 캐야 하니, 각 구간의 threshold를 구한다.
        
        //* 각 구간에 대해 모든 곡괭이 값을 구하고 최소값으로 갱신
        
        //* 필요한 tresh 칸 수 = 최대: 곡괭이 수, 최소: minerals.length / 5 + 1
        
        //* 각 구간에 대한 곡괭이 사용 값
        // int[][] thresh = new int[Math.min(picksCount, (minerals.length/5) + 1)][3];
        int[] temp = { 0, 0, 0 };
        for(int i = 0; i < minerals.length; i++){
            if(i > 0 && i % 5 == 0){
                pq.offer(new int[]{
                    temp[0], temp[1], temp[2]
                });
                
                temp[0] = 0;
                temp[1] = 0;
                temp[2] = 0;
            }
            
            if(i >= picksCount * 5) break;
            
            switch(minerals[i]) {
                case "diamond":
                    temp[0] += 1;
                    temp[1] += 5;
                    temp[2] += 25;
                    break;
                case "iron":
                    temp[0] += 1;
                    temp[1] += 1;
                    temp[2] += 5;
                    break;
                default:
                    temp[0] += 1;
                    temp[1] += 1;
                    temp[2] += 1;
                    break;
            }
        }
        
        if(temp[0] != 0 || temp[1] != 0 || temp[2] != 0){
            pq.offer(new int[]{
                    temp[0], temp[1], temp[2]
                });
        }
        
        
        while(!pq.isEmpty()){
            int[] current = pq.poll();
            
            for(int i = 0; i < picks.length; i++){
                if(picks[i] != 0){
                    answer += current[i];
                    picks[i]--;
                    break;
                }
            }
        }
        
        return answer;
    }
}

Problem

문제 설명

마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

• 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

제한사항

• picks는 [dia, iron, stone]과 같은 구조로 이루어져 있습니다.
  • 0 ≤ dia, iron, stone ≤ 5
  • dia는 다이아몬드 곡괭이의 수를 의미합니다.
  • iron은 철 곡괭이의 수를 의미합니다.
  • stone은 돌 곡괭이의 수를 의미합니다.
  • 곡괭이는 최소 1개 이상 가지고 있습니다.
• 5 ≤ minerals의 길이 ≤ 50
  • minerals는 다음 3개의 문자열로 이루어져 있으며 각각의 의미는 다음과 같습니다.
  • diamond : 다이아몬드
  • iron : 철
  • stone : 돌

입출력 예

입출력 예 설명

입출력 예 #1

다이아몬드 곡괭이로 앞에 다섯 광물을 캐고 철 곡괭이로 남은 다이아몬드, 철, 돌을 1개씩 캐면 12(1 + 1 + 1 + 1+ 1 + 5 + 1 + 1)의 피로도로 캘 수 있으며 이때가 최소값입니다.

입출력 예 #2

철 곡괭이로 다이아몬드 5개를 캐고 돌 곡괭이고 철 5개를 캐면 50의 피로도로 캘 수 있으며, 이때가 최소값입니다.

오늘은 알고리즘 중 Backtracking 기법을 다뤄보려 한다.

Backtracking
- 한정 조건을 가진 문제를 풀려는 전략
- 해를 얻을 때까지 모든 가능성을 시도

출처 https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89

위키피디아의 설명처럼, 해를 얻을 때 까지 모든 가능성을 시도하는데, 완전 탐색과의 다른 점은 "신경쓰지 않아도 되는 수는 배제한다." 는 큰 차이점이 있다.
내가 원하는 답을 찾을 때 까지 탐색하며, 만약 해당 길을 통해 답을 찾을 수 없다면, 가능한 이전 길까지 돌아가서 다음 길을 찾는 방법을 채택하게 된다.

주요 전략

퇴각기법을 풀이 할 때는, 전략이 중요하다. 동적계획법의 경우, 주요 전략이 "1. 점화식을 찾고, 2. 재귀로 표현한다." 2가지 였다면, 퇴각기법에는 총 3가지 주요 전략이 존재한다.

1. Choices, 선택

먼저, 어떤 선택을 할지 결정해야 한다. 본문 상단에 언급한 바와 같이, 해를 얻을 때까지 모든 가능성을 시도하는데, 어떤 시도를 할지 결정해야 한다. 완전탐색은 정말 모든 수를 탐색하지만, 백트래킹은 내가 할 수 있는 모든 가능성만 시도하기 때문에 차이가 있다. 즉, 내가 현재 선택한 답은 유효하다고 가정한다.

2. Constraints, 제약 조건

그 다음으로, 내가 이 선택을 했을 때 어떤 제약이 발생할 지 알아야 한다. 답을 찾기 위해 탐색할 때, 나의 선택을 방해하는 제약조건이 무엇인지를 명확히 정의해야 내 선택으로부터 정답까지 다가갈 수 있다.

3. Goal, 목표

마지막으로 내가 풀고자 하는 문제를 정의해야 한다. 내가 지금 풀고자 하는 문제의 목표가 무엇인지 정의하지 않는다면, 문제를 푸는 의미가 없기 때문이다.

탐색 방법

퇴각기법의 탐색은 보통 재귀로 표현한다. 이 때, 다음과 같은 탐색을 따르는 것이 좋다.

1. 선택
2. 조건 확인
3. 선택 취소

이 때, 1번과 2번의 순서는 바뀌어도 무방하다.

우선, 어떤 답을 선택한 뒤, 해당 답이 제약조건에 위배되는지 확인한다. 위배되지 않는다면, 해당 답은 유효하다 가정하고, 다음 선택을 진행, 풀이를 반복한다.
해당 선택에 대한 풀이가 끝에 도달하면 선택을 취소하는데, 그 이유는 해당 선택이 다른 선택으로부터 도출되는 경로에서는 "정답"이 아닐 수도 있고 따라서 해당 선택을 계속 유효한 상태로 둔다면, 다른 정답이 옳바른 정답을 찾는데 방해될 수 있기 때문이다.

N Queen 예시

N Queen은 N*N체스보드 위에서 퀸 끼리 서로 공격할 수 없는 곳에 위치시켜 각 N열 혹은 N행마다 적어도 하나의 퀸을 위치시키는 문제다. 퀸은 체스보드 위에서 가로, 세로, 대각선 방향으로 이동할 수 있으며, 이 위에 상대 말이 있다면 해당 말을 잡아먹을 수 있다.
다음 그림처럼 4*4 (1~4, 1~4) 체스판이 있다하자.

이 때, 첫 칸에 퀸이 존재한다면, 다른 퀸은 초록색 사각형에 걸쳐진 위치에만 존재할 수 있다. 다음 줄 예를 들어보자.

왼쪽 사진을 보면, (2, 3)의 위치에 퀸을 두게 되면 나머지 3, 4번째 줄에 퀸을 놓을 수 없게 되고, (2, 4)의 위치에 놓았을 때 주황색과 같은 위치에 놓을 수 있게 된다. 하지만, 이 경우 마찬가지로 (3, 2)에 퀸을 위치시키게 되면 4번째 위치에는 퀸을 놓을 수 없으므로 정답을 찾을 수 없다.
이 때, 이전 선택인 (2, 4)로 돌아가 다음 (3, i)를 선택하는데, 다른 선택은 존재하지 않으므로 (1, 1)로 돌아가 (2, i)를 선택한다. 하지만 마찬가지로, (1, 1)에서 할 수 있는 선택은 모두 소모되었으므로, 최종적으로 퀸은 (1, 1)에 놓을 수 없다고 판단하여 (1, 2)에서부터 같은 탐색을 진행한다.

전략 풀이

1. Choices: 퀸을 놓을 자리
2. 제약조건: 앞으로 놓을 퀸에 대하여, 가로, 세로, 대각선에 대해 위배하는가? 이 때, 가로는 어차피 놓을 수 없기 때문에 제외한다.
3. 목표: 각 N줄 마다 퀸이 존재하도록 위치를 잘 정한다.

1. Chocies

N 보드에 대해, 한 줄 마다 퀸을 놓을것이며, 따라서 다음과 같은 생김새를 갖는다.

FOR i = 1 TO N
board[currentColumn] = i
IF constraints(board, currentColumn) THEN
findNext(board, currentColumn+1)
END IF
board[currentColumn = 0
END FOR

이 때, currentColumn은 현재 내가 찾고 있는 줄이고, constraints는 제약조건을 검사하는 함수, findNext는 답을 찾는 함수다.

2. Constraints

제약조건은 세로, 대각선에 대해 검사하면 되고, 따라서 다음과 같은 생김새를 갖는다.

FOR i = 1 TO col
IF board[i] == board[col] THEN
return FALSE
ELSE IF | col - i | == | board[col] - board[i] | THEN
return FALSE
END FOR

return TRUE

i ~ col 까지 반복하는 이유는, 내 다음 줄에는 퀸이 없고, 따라서 다음줄에 존재하는 퀸으로 하여금 내 이동에 제약이 생기지 않기 때문이다.
세로검사는 이전 줄의 queen이 나와 같은 행에 존재하는지 검사하면 된다.
그 다음으로 대각선의 위치를 검사하는데, col - i는 현재 내 행과 다른 행의 떨어진 거리가 실제 내 퀸이 놓인 위치와 해당 열에서 퀸이 어디에 존재하는지 의 거리를 검사하면 된다.

예를 들어, (3, 4)에 퀸이 위배되는지 검사한다고 가정하자. 이 때 i의 값은 1~4, col의 값은 3이 된다. 내가 대각선에 있는 것을 알기 위해서는 다음 행에 대해, 바로 다음 열(1) + 1 혹은 - 1, 혹은 그 다음 열(2) +2 혹은 -2, ... 의 값에 존재하는지 확인하면 된다.

대각선 구하는 방법
1행: 열에 대해 +1, -1
2행: 열에 대해 +2, -2
3행: 열에 대해 +3, -3

열 = |행|의 값 이해가 안간다면 직접 그려보자.

예를 들어, (3, 4)에 퀸이 위배되는지 검사한다고 가정하자. 이 때 i의 값은 1~4, col의 값은 3이 된다. 내가 대각선에 있는 것을 알기 위해서는 다음 행에 대해, 바로 다음 열(1) + 1 혹은 - 1, 혹은 그 다음 열(2) +2 혹은 -2, ... 의 값에 존재하는지 확인하면 된다.

대각선 구하는 방법
1행: 열에 대해 +1, -1
2행: 열에 대해 +2, -2
3행: 열에 대해 +3, -3

열 = |행|의 값 이해가 안간다면 직접 그려보자.

남은 것은 탐색

이제 탐색을 수행하면 된다. 코드작성의 경우, 알고리즘 문제풀이에서 진행하도록 하겠다.
잊지 말자!

"선택 → 제약 → 목표" 그리고 "선택 → 제약 → 선택취소"

드디어 첫 알고리즘과 관련된 게시글을 작성한다! (짝짝짝)

동적 계획법, 말만 들으면 무슨말인지 모르겠다. 느낌적으로는 뭔가 활발하게(?) 바뀌는 느낌인데, 다음과 같은 프로그래밍을 칭한다.

하나의 문제를 여러 문제로 나누어 푸는 방법

예를 들어서, 우리가 1~10까지의 합을 계산할 때, 하나의 문제는 다음과 같이 존재한다.

1+2+3+...+8+9+10 = 55
- 물론 n*(n+1) / 2 로 풀 수도 있다. 그치만 그게 중요한게 아니니까!

이를 여러 문제로 나누게 되면, 다음과 같이 바뀌게 된다.

1+2 = 3
1+2+3 = 3+3 = 6
1+2+3+4 = 6 + 4 = 10
1+2+3+4+5 = 10 + 5 = 15
1+2+3+4+5+6 = 15 + 6 = 21
...
1+2+3+...+8+9+10 = 45 + 10 = 55

왜?

동적 계획법은 문제를 빠르게 풀 수 있다는 장점이 존재한다. 위에서 예로 든 1~10까지의 합을 계산 할 때, 마지막 합을 계산할 때 이미 앞 단계의 합은 계산되어 있는것을 알 수 있다. 즉 1~N까지의 합을 구하기 위해 O(n)만에 풀 수 있는 것이다.

동적 계획법을 이미 알고 있는 사람이라면, 어? 예시가 잘못 된거 아니야? 원래 1~N까지의 합은 O(n)안에 풀리는데? 라고 생각할 수 있다.

물론 맞는말이다! 하지만, 동적 계획법을 모르는 사람이 공부를 시작한다면, 처음부터 피보나치, 연속 합, 합 만들기, 파도반 수열, 길 찾기, ... 등으로 예시를 든다면, 처음부터 이해가 안갈 것이고, 따라서 정~~말 쉬운 것부터 풀어보고자 위의 예시를 들었다.

N단계를 풀 때, 이미 N-1단계는 계산되어 있다.

피보나치 수열

항: (0) 1 2 3 4 5 6  7   8 ...
수: (0) 1 1 2 3 5 8 13 21 ...
점화식 F
Fn+2​= Fn+1​+ Fn​ = Fn-2 + Fn-1

피보나치 수는 앞 선 두 항의 합이 현재 항이 되는 수열을 나타낸다. 다시말해 F(6)을 풀기 위해서는 F(6) = F(5)+F(4)에 대한 연산을 수행해야 한다. 이를 동적계획법을 사용하지 않고 나타낸다면, 다음과 같은 연산이 필요하다.

사람같은 경우에 F(5) = 5라는 것을 직감적으로 알 수 있지만, 컴퓨터는 모른다. 따라서 매 번 요청 할 때마다 연산을 수행해야 한다.

해당 트리를 잘 보면, 2를 연산하기 위해 1, 0을 호출하고, 3을 연산하기 위해 2, 1을 호출하고, ..., 겹치는 연산이, 재귀적인 호출이 굉장히 많다. 또한 이 연산을 위한 시간 복잡도를 계산해 보면 O(2^n)이라는 큰 복잡도를 가진다.

Tree의 Height = Depth = 5
Tree의 Level이 증가함에 따라(Height가 감소함에 따라) Fib(N)의 N이 하나씩 줄어들고, 결국 N을 계산하기 위해 각 레벨에서 N - 1씩 연속적으로 호출한다.
N => N-1, N-2 => (N-2, N-3), (N-3, N-4) => ( (N-3, N-4), (N-4, N-5) ), ( (N-4, N-5), (N-5, N-6) ) ...
→ N에 대하여 2^n 만큼 증가!

이러한 시간복잡도를 줄이기 위해(문제를 해결하기 위해) 동적 계획법을 사용하면 꽤나 빠른 시간 안에 연산할 수 있다.

동적계획법을 활용하지 않으면, 사라진 노드들에 대해 일일히 모두 계산해줘야 하지만, 동적계획법을 사용함으로써 fib(3)의 값이 2임을 이미 알고있고, 따라서 fib(3)의 연산을 추가적으로 하지 않은 것을 확인할 수 있다.

// fibonacci 연산 값을 저장할 배열
int[] fibonacci;

// fibonacci 값을 연산하는 함수
func setfib(limit)
  fibonacci[0] = 0;
  fibonacci[1] = 1;
  for i -> 2 to limit
    fibonacci[i] = fibonacci[i-2] + fibonacci[i-1];
  end for
end func

// 찾고자 하는 피보나치 수를 반환하는 함수
func getfib(N)
  return fibonacci[N]

시간복잡도는 O(n)안에 풀 수 있다.

그 이유는..위 트리를 보세요..ㅎㅋㅎㅋ

정리하면서,

우선

동적 계획법을 사용하려면, 풀고자하는 문제의 점화식(규칙)을 찾아야한다. 위에서 예로 든 피보나치의 경우, F(N) = F(N-2) + F(N-1)과 같은 식 말이다.

문제마다 식이 다르기 나오기에, 어떻게 해라! 라는게 딱히 없다. 다만, 규칙을 찾을 때 까지 수를 나열해 보거나, 문제로부터 힌트를 얻는 방법 밖에 없다.

피보나치와 같은 문제는 수를 나열하며 규칙을 찾을 수 있을 것이고, Working Days Problem과 같은 경우에는, 문제로부터 힌트를 얻을 수 밖에 없다. (하루 건너 일할 때 가장 돈을 많이 버는 경우는 마지막 날에 일을 하냐 안하냐로 판단할 수 있는것 처럼.)

끝으로

동적 계획법은 다음과 같은 문제를 풀 때 사용하면 좋다.

1. 중복되는 풀이를 할 때
2. 재귀로 풀면 시간 복잡도가 클 때

오늘은 백준 2775번 부녀회장이 될테야 풀이를 할 예정이다. 그간 이런저런 일이 많아서 블로그에 소홀했는데,, 여튼! 시작해보자

바로 본론으로 들어가서,,

a층 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들 수의 합만큼 사람들을 데려와 살야아 한다. 이 때, 0층 N호에는 총 N명이 산다.
→ 0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.
→ 1층 3호에 살려면 6명, 2층 3호에 살려면 10명을 데려와 살아야 한다.

문제에 따르면 1층 3호에 살려면 6명은 다음과 같이 구해진다

(1-1)층 1호~3호까지 사람의 수의 합 = 0층 1호 + 0층 2호 + 0층 3호 = 1 + 2 + 3 = 6명 이다.

마찬가지로, 2층 3호의 사람을 구해보면 (2-1층) 1호~3호까지 사람 수의 합 = 1층 1호 + 1층 2호 + 1층 3호 = 1 + 3 + 6 = 10명

잘 보면, subtree가 반복되는걸 확인할 수 있다. 만약 3층 4호, 5층 6호 ... 로 확장해 나갈수록, k-1, k-2, k-3, ... (k-m >= 0)이 반복되고 이에 대응하는 n호에 대한 사람 수도 subtree에서 반복되어 나타날 것이다. (만약 머리에 안그려진다면, 직접 그려서 확인하는걸 추천한다.)

subtree가 반복될 때 우리는 Dynamic Programming을 통해 쉽게 해당 문제를 풀 수 있다. 층에 대한 사람 수를 결정해 놓고, 해당 호수를 출력하면 문제 풀이는 끝이난다.

→0층 1호에는 1명, 2호에는 2명, ..., 14호에는 14명 이 산다.

위 조건에 맞게, 1호~14호 까지는 1~14의 값을 넣어주고, 이후 층 부터 (k-1)층 n호에 대한 사람 수를 불러와 더해주면 된다.

문제 풀이를 위해 1차원 배열을 선언하고, 14개씩 끊어서 하나의 층을 표현할 예정이다.

        for(int i = 14; i < rooms.length; i++){
            int floor = i / 14;
            int number = (i % 14) + 1;
            int underFloor = floor-1;
            int underValue = 0;
            for(int j = 0; j < number; j++){
                underValue += rooms[underFloor * 14 + j];
            }
            rooms[i] = underValue;
        }

따라서 위의 표정을 보면, 층수는 ( i / 14 )의 값을 갖게 되고, 호수(number)는 ( i % 14 ) +1이 된다. 1을 더해준 이유는, 실제 호수는 0~13이 아닌 1~14호기 때문이다.

이후 아래층의 1호~number호 까지의 방에 살고있는 사람수 (underValue)를 계산한다. 이 때, underFloor*14인 경우는 1차원 배열로 선언했기 때문에, 바로 아래층의 위치를 구하기 위해 14를 곱해줘야 하기 때문이다.

최종 코드

public class Number2775 {
    public static void main(String[] args) throws IOException {
        int[] rooms = new int[15*14];
        for(int i = 0; i < 14; i++){
            rooms[i] = i+1;
        }
        for(int i = 14; i < rooms.length; i++){
            int floor = i / 14;
            int number = (i % 14) + 1;
            int underFloor = floor-1;
            int underValue = 0;
            for(int j = 0; j < number; j++){
                underValue += rooms[underFloor * 14 + j];
            }
            rooms[i] = underValue;
        }

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            int k = Integer.parseInt(br.readLine());
            int n = Integer.parseInt(br.readLine());
            System.out.println(rooms[k * 14 + (n-1)]);
        }

    }
}

rooms의 배열이 14 * 14가 아닌 이유는, 아파트의 층수가 0층~14층까지 존재하기 때문에 총 15개의 층에 대해 연산해야 하기 때문이다.

결과는.. 정답!

오늘은 백준 벌집 문제를 풀거다. 한번에 맞추지 못했다. 배열 써서 풀려 했는데, 이유 모를 OutOfBounds 오류와 배열 사용으로 인한 메모리 초과 오류가 발생했다. 심지어 정답직전에 테스트 출력까지 포함해버려서 (...) 총 6번의 리트만에 정답... OutOfBounds는 도저히 내 컴퓨터에서 재현이 안된다... 1~10억까지 다 넣어봤는데..난 안난다....

벌집 문제

문제를 딱 보면, "... 최소 개수의 방을 지나서 갈 때 ..."로 인해 Shortest Path를 찾는 것인가 싶다.
하지만 그림을 잘 보면, 규칙이 있다.

이 규칙을 찾았으면, 다음 규칙도 보인다.

벌집의 겉에는 원자의 전자껍질과 같은 구조를 발견할 수 있다. 심지어 해당 껍질은 등비수열을 이룬다. 그리고 제일 안쪽 껍질은 무조건 밟아야 함에 착안해서, 두 번째 껍질의 시작을 1로 맞춰주면 문제를 풀기 더 쉽다.
$$ a_n = 6^{(n-1)} $$
벌써 문제를 다 풀어버렸다.

입력값으로 N이 주어지고, 해당 N까지의 거리를 구해야 한다. 껍질의 시작을 1로 맞춰주기로 했으니, 입력값 N에서 1을 빼준다.

N = N - 1 ~> 두 번째 껍질의 시작을 1로 맞춰주기 위함

그리고 껍질의 층 수를 나타내는 변수 base와 껍질을 벗겨내는 반복자를 이용하여 한 층 씩 벗겨내면 된다. 벌집의 방 번호는 항상 양수이기 때문에, 현재 껍질이 음수가 되어서는 안된다.
이를 위한 연산을 입력값과 벗겨낼 껍질 층으로 구할 것이다. 입력 값을 N, 반복자를 i라 할 때, 다음과 같다.

입력 값: N
현재 껍질 수: i
현재 껍질 층: base

다음 껍질 수 i = i + 6 * (base+1);
남은 입력 값 N = N - i

위 내용을 바탕으로 수도코드로 정리하면 이렇게 된다.

WHILE ( N - i >= 0) THEN
i = i + 6 * (base);
base += 1;
END WHILE

이후 While문이 종료되면 base는 입력 값 N에 대한 껍질 층이 반환되고, 이 값은 1로부터 얼마나 떨어져있는지가 된다.

최종 코드

import java.util.Scanner; public class Number2292 { public static void main(String[] args){ Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int temp = N-1, base = 1, i = 1; while(temp - i >= 0){ System.out.print("bef: " + i); i += 6 * (base++); System.out.println(", aft: " + i + ", cal: " + temp); } System.out.println(base); } }

결과는 정답!

오늘은 백준 3052번 문제를 풀자! 해당 문제를 봤을 때, 바로 떠오른 방법이 두 가지가 있다.

MkWeb을 개발하면서 HashMap을 엄청나게 썼기 때문에, 첫 번째로 HashMap이 떠올랐고, 그 다음으로 Queue를 이용한 풀이가 떠올랐다.

해시맵의 경우, 중복되는 키를 허용하지 않기 때문에 나머지를 구한 다음에 HashMap에 각각 넣어준 뒤, HashMap의 사이즈를 반환하면 끝이다. 너무 쉽기 때문에, Queue를 이용하여 문제를 풀이하려 한다.

사실 큐를 이용하나 ArrayList, Stack 등 다른 자료구조를 이용하나 풀이는 비슷하지만, 큐의 풀이가 더 직관적이기 때문에 큐를 선택했다.

이쯤 되면 나머지 수를 구하는 것은 쉬우니, 설명은 넘어가도록 하겠다.

val = 입력값 % 42

우리는 큐에 값을 하나 씩 넣어줄 예정인데, 이전에 큐에 이미 값이 존재하는지 확인해야 한다. 이 때, 값이 존재하지 않는다면 값을 추가하고, 존재한다면 해당 값은 따로 추가하지 않을 것이다.

이때 '하나의 큐로 어떻게 가능하지?'라는 의문이 들텐데, 당연히 두 개의 큐를 사용할 것이다. (물론, 하나는 배열, 하나는 큐 등 어떤 형태를 취하든 상관 없으나, 위에서 말한대로 큐가 직관적이기 때문에 큐를 사용할 것이다.)

mainQueue: 나머지가 저장될 큐
tempQueue: mainQueue에 존재하지 않는 val들을 임시적으로 저장할 큐

매 회차마다 mainQueue로부터 tempQueue로 하나씩 옮겨담을 것이다. 이 때, val이 mainQueue에 존재하는지 확인하고, 존재하지 않는다면 값을 추가할 것이다.

따라서 mainQueue에서는 dequeue가 주로 사용될 것이며, tempQueue에는 enqueue가 주로 사용될 것이다.

While size of mainQueue > 0 Then
    peek is mainQueue.dequeue();
    If peek is not val Then
        tempQueue.enqueue(peek);
    End If
End While

수도 코드를 표현하려 했는데.. VB의 아련한 기억이...

while 반복문이 끝나면, queue를 tempQueue로 바꿔주고, queue에 val을 추가해주면 된다. val을 추가하는 이유는 while문 내에서 val을 제외한 값들만 옮겨 넣었기 때문에, mainQueue에는 val이 없다.

최종적으로 mainQueue의 size를 출력해주면 해당 문제는 끝!

전체 코드

import java.io.*;
import java.util.*;

public class Number3052 {
    public static void main(String args[]) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < 10; i++) {
            int val = (Integer.parseInt(bufferedReader.readLine())) % 42;
            Queue<Integer> tempQueue = new LinkedList<>();
            while(queue.size() > 0) {
                int peek = queue.poll();
                if(peek != val){
                    tempQueue.add(peek);
                }
            }
            queue = tempQueue;
            queue.add(val);
        }

        System.out.println(queue.size());
    }
}

결과는 정답!