알고리즘(코딩테스트)
백준 2292번 벌집(JAVA)
qbang
2024. 3. 4. 22:30
2292번: 벌집
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌
www.acmicpc.net
풀이코드
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int target = Integer.parseInt(st.nextToken());
int pass = 1; // 숫자 1로부터 지나온 방 수
int max = 0; // 탐색한 영역에 써있는 숫자의 최댓값
while (max < target) { // 아직 타겟 숫자보다 찾은 숫자가 더 작으면
pass += 1; // 지나온 방 수를 증가
max += (6 * pass); // 숫자의 최대값 갱신
}
System.out.println(pass + 1); // 시작점을 포함하므로 1이 써져있는 방을 더해준다
}
}풀이과정
숫자 1을 기준으로 붙어있는 숫자들의 규칙을 찾는다.
지나쳐 온 방(pass)이 0일 때 탐색한 숫자 중 가장 큰 숫자는 1이다.
문제에 시작과 끝을 포함한다고 되어 있으니 만약 숫자 1을 찾는다면 지나온 방 수는 1이다.
지나쳐 온 방(pass)이 2일 때 탐색한 숫자 중 가장 큰 숫자는 7이다.
지나쳐 온 방(pass)이 2일 때 탐색한 숫자 중 가장 큰 숫자는 19이다.
지나쳐 온 방(pass)이 3일 때 탐색한 숫자 중 가장 큰 숫자는 37이다.
지나쳐 온 방이 4일 때는 61, 5일 때는 91 ...
가장 큰 숫자를 나열해보면 1, 7, 19, 37, 61, 91 ... 각 숫자의 차이는 6, 12, 18, 24, 30 ... 지나쳐 온 방이 증가할수록 6의 배수가 더해지고 있는 것을 찾을 수 있다.
이를 코드로 나타내어 지나쳐 온 방에서 찾을 수 있는 가장 큰 수(max)를 찾아준다.
max += (6 * pass); // 숫자의 최대값 갱신max는 지나쳐 온 방 수 * 6의 배수만큼 증가한다.
while (max < target) { // 아직 타겟 숫자보다 찾은 최대값이 더 작으면
pass += 1; // 지나온 방 수를 증가
...만약 입력값이 max보다 작으면 현재는 찾을 수 없는 값이므로 max를 증가시켜준다.
만약 max가 더 크다면 찾을 수 있는 값이므로 반복문을 즉시 종료하고, 시작점을 포함하므로 지나온 방 수 + 1을 출력시켜야 한다.