[백준] 벌집 JAVA

반응형

728x90

[백준] 벌집

---

접근

• DFS
• 규칙 찾기

---

풀이

백준 사이트에서도 문제를 풀기 시작했다. 백준에서는 천천히 solved.ac의 클래스 추천에 뜨는 문제들부터 차근차근 푸는 중이다. 아직 브론즈 1 티어로 주로 쉬운 문제들이라 빨리빨리 넘어가던 중 흠칫하게 만든 문제가 있어 들고 왔다.

 

문제를 처음 봤을 땐 프로그래머스에서 삼각 달팽이?라는 이름의 문제가 있었는데 그 문제가 떠올랐다. 2차원 배열을 이용해 숫자를 채우는 그런 문제였는데 이 문제도 그런 방식으로 숫자를 채워두고 DFS 같은 걸로 구해야 하나 생각했다. 하지만 이 문제의 조건인 N의 입력 범위가 1,000,000,000까지로 배열에 단순 숫자 채우기도 시간 초과가 날 숫자이고 무엇보다 브론즈 티어의 문제라 단순한 방법이 있을 거라 생각했다.

 

정말 그림이 알아보기 힘들었지만 그림을 자세히 보다 보면 가운데 방인 1을 중심으로 원형으로 커지고 있고 둘러 쌓인 원의 방은 6의 배수의 개수로 늘어나고 있다. 처음 1번을 둘러싼 2~7번 방의 개수는 6개, 2~7번 방을 둘러싼 8~19번 방의 개수는 12개 이런식으로 6개씩 늘어나는 구조로 되어 있었기에 마지막 방의 위치를 찾는다는 것은 즉 마지막 방이 몇 번째에 테두리에 있냐를 묻는 것과 같다.

if (N == 1) {
  System.out.println(1);
  return;
}
        
int layer = 1; 
int maxRoom = 1;

n이 1일 경우 처리를 해주고 계층을 나타내줄 layer 변수와 방 번호 체크를 위한 변수를 선언한다.

while (true) {
  maxRoom += 6 * layer;           
  layer++; 
  
   if (N <= maxRoom) {
	System.out.println(layer); 
	return;
  }
}

maxRoom은 해당 계층의 마지막 방 번호를 나타낸다. 그러므로 목표 방 번호가 maxRoom 보다 작다면 같은 계층에 존재한다는 의미로 해당 계층의 층 수가 1번 방에서의 최단 거리가 된다.

---

전체 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        if (N == 1) {
            System.out.println(1);
            return;
        }
        
        int layer = 1; 
        int maxRoom = 1; 
        
        while (true) {
            maxRoom += 6 * layer; 
            layer++; 
            
            if (N <= maxRoom) {
                System.out.println(layer); 
                return;
            }
        }
    }
}

백준 사이트는 기본적으로 만들어주는 틀 없이 백지에서 처음부터 다 써야 하기에 매번 타자를 치기가 너무 귀찮다.프로그래머스와 구름은 기본 틀도 만들어 주고 테스트 케이스 실행시 결과나 내가 출력을 찍어 확인도 해볼 수 있는데 여기는 그런 거 없이 바로 제출이 되더라. IDE 없이 사이트에서 바로 코딩을 하니 너무 불편함이 많고 나중에 복잡한 문제들은 IDE 없이 풀 수 있을지 모르겠다.