본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[ACM ICPC 기출, 백준 2292번] 벌집 문제 풀이 및 해설 (C++/Java 문제 풀기~)

ACM-ICPC 서울 2004 online round 문제 B번

백준 2292번 (번역본)

분류 : 규칙 찾기

[2292번] 벌집

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지 (시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들어 13까지는 3개 58까지는 5개를 지난다.

조건

시간 제한: 2초

메모리 제한: 128MB

정답 비율 56.56%

입출력

입력: 첫째 줄에 N(1<=N<=1000,000,000)이 주어진다.

출력: 입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 며 개의 방을 지나는지 출력한다.

참고로 이 입력의 첫째 줄은 테스트케이스이므로 무시!

 

같이 풀어봐요~~~ 


ANSWER

문제는 어려워보이지만.. 쓸데없이 그림이 들어가서;;

막상 읽어보면 쉬움을 알 수 있죠 ㅎㅎ 고등학교 때 다져진 수학 내공이란 ㅎㅎㅎ

딱 보자마자, 아 ~ 몇 번째 레이어인지 찾는거네 수열 문제구먼! 했다면 정답입니다!! 짝짝

 

규칙을 찾아볼게요

처음과 끝을 포함하니, 첫 레이어는 1이겠고

2 layer는 2~7 -> 6개

3 layer는 8~ 19 -> 12개

4 layser는 20~37 -> 18개

 

오 규칙이 보여요 ㅎㅎ 여러분도 찾았나요?ㅎㅎ

2에다가 6을 더하면 8 거기다가 또 6+6을 더하면 20, 거기다가 6+6+6을 더하면 38...!

Java 코드

[벌집 - Java]

요 규칙을 이용한 풀이입니다. 

import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		System.out.println(countBang(num));
	}
	public static int countBang(int n) {
		int sum=2; int layer=0;
		if(n == 1)
			return 1;
		while(n>=sum)
			sum+= 6*(layer++);
		return layer;
	}
}

만약 수가 15이면, 15<20일 때 반복문을 빠져나오고 결과를 반환해줘야겠죠?

근데 20은 사실 3레이어가 아니라 4레이어잖아요 그러므로 마지막에 ++를 해줍시다!

[벌집 Java - 계차수열 일반항으로 풀기]

사실 고딩때 수학을 배웠던 사람이라면 이거 연필로 풀면 계차수열 일반항 구해서 풀잖아요 ㅎㅎ

더 좋은 방법은 아니지만 고렇게 풀어볼 수 있을 것 같아서 한번 풀어보겠숩니다.

먼저 계차수열 bn은 이렇게 되므로

요 공식에 의해 일반항 an은 an = 2+ 3(n-1)(n-2) (n>1)가 되겠죠? 한 번 확인..

n=1일 때는 1 (예외처리 필요)

n=2일 때는 2, n=3일 때는 8, n=4일 때는 20 .. 굳!

import java.io.IOException;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		System.out.println(countBang(num));
	}
	public static int countBang(int bangNumber) {
		int layer =1, sum=0;
		if(bangNumber==1)
			return 1; //1항은 예외처리
		while(bangNumber>=sum) {
			layer++;
			sum= 2+3*(layer)*(layer-1);
		}
		return layer;
	}
}

마찬가지로 만약 수가 15이면 15<20일 때 빠져나오겠죠? sum이 20일 때 layer는 사실 4지만 우리가 정답으로 반환해야 할 답은 3이예요 ㅎㅎ

반복문 내에서 ++를 해주고 있는데 마지막에 --해주는게 번거로워 보여서 an을 2+3(n-1)(n-2)를 사용하기보다 2+3n(n-1)을 사용해줬어요. 이렇게 하면 3레이어일때도 실질적으로 4레이어로 계산되어 똑같은 판별식이 되겠죠?

C/C++ 코드

[벌집 - C++]

똑같은 풀이를 C언어로 풀어볼게요 ㅎㅎ설명은 자바쪽에서 상세히 했으니까 반복되는 말은 생략할게요

while문을 for문으로 바꿨을 뿐..

#include <iostream>
using namespace std;
int main() {
	int num, layer = 0;
	cin >> num;
	for (int sum=2 ;sum<=num ; layer++)
		sum += 6 * layer;
	if (num == 1) layer = 1;
	cout << layer;
}

[다른 사람 풀이로 배우기1]

요렇게 거꾸로 접근하는 방법도 있네요 ㅎㅎ

오늘 풀이는 여기까지입니다 ㅎㅎ!

공감과, 덧글 또는 광고보답은 정보제공에 큰 힘이 됩니다 :) 다음 포스팅에서 또 봐요!