[C++] 백준 온라인 저지 2292

문제

---

www.acmicpc.net/problem/2292

2292번: 벌집

설계

---

먼저 이 벌집의 규칙성은 다음과 같다.

이 그림에서, 같은 크기의 방 (같은 색깔로 색칠 된 곳)을 도는 수
즉, 층을 i라고 가정할 때

i 가 1일때는 1 (예외처리)
i 가 2일때는 2~7
i 가 3일때는 8~19
....

의 범위 안에 숫자들을 포함한다. 즉, 1층엔 1, 2층엔 2~7 3층엔 9~36번의 숫자가 포함된다.
그리고 층이 끝나는 지점의 숫자를 기점으로 나열해본다면.

노션 최고야!!

이런 규칙성을 찾을 수 있다. 즉 계차가 6인 계차수열이다.
(사실 계차수열이란 것도 까먹었음, 고딩 졸업한지가 언젠데... 검색해보고 알았다.)

아무튼 그래서, 2중for문으로 돌면 괜찮지않을까 ? 해서 짰던 코드가 다음과 같다.

#include <iostream>

using namespace std;

int main(void){
    cout << "시작" << endl;
    int n, cnt = 0;
    cin >> n;
	
	if(n == 1){
		cout << 1;
	} else {
		for(int i = 1; i < n; i++){
			for(int j = 0; j < n ; j += i*6){
				if(n > 1 && n <= i*6){
					cout << i;
					break;
				}
			}
		}
	}
	
    return 0;
}

결과적으론 이상한 코드다. 이게 뭐냐면..
i 가 층이고, 이 층마다 6번씩 j가 도는데, n이 이 층에 포함되어있으면 i + 1을 출력하는.. 고런...코드다.

뭔가 이건 아니다 싶어서 코드를 싹 지우고 생각해봤다. 그래서 다음과 같다.

코드

---

#include <iostream>

using namespace std;

int main(void){
    int n, cnt = 0;
    cin >> n;
	
	if(n == 1)
		cout << 1;
	else {
		for(int i= 2; i <= n ; cnt++){
			i += 6 * cnt;
		}
		cout << cnt;
	}
    return 0;
}

코드를 한번에 줄였다. 생각보다 간단한 거였음..

일단 1일때는 예외처리 해버리고,
i가 위에서 말한 층이 끝나는 숫자, 즉 1, 8, 17 .. 을 넘을 때만 for문을 돌게끔 하면 깔끔하게 결과가 도출된다.

처음에 짰던 내 코드는 for문을 엄청 많이 돌아서 비효율 적이었는데, 이렇게 짜면 시간단축에 훨씬 도움이 된다는 것을 알았다.

참고로 이 문제는 계차수열의 공식을 이용해서도 풀이가 가능하다. 링크로 걸어놓는다.

jhnyang.tistory.com/211

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

 

결과

---

 

 

구독 및 하트는 정보 포스팅 제작에 큰 힘이됩니다♡