[#47][알고리즘] 벌집
백준 > 벌집
문제 링크(https://www.acmicpc.net/problem/2292)문제
.png)
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
출력
입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.
예제 입력 1
13
예제 출력 1
3
#include <iostream>
using namespace std;
int main() {
int number,max=1 ,min =2,n=1;
cin >> number;
if (number == 1) {
cout << 1 << endl;
return 0;
}
while (1) {
max += 6 * n;
min += 6 * (n - 1);
if (number >= min && number <= max) {
cout << n+1 << endl;
break;
}
else
n++;
}
return 0;
}
| cs |
1
2~7
8~19
20~37
38~61
...
max 초기값 1
min 초기값 2
입력값이 1일 경우 : 1 출력 후 종료
아닌 경우
예) 38
n = 1
max = (6 * 1) + 1 = 7
min = (6 * 0) + 2 = 2
입력값이 2~7 사이에 있지 않음.
n++
n = 2
max = 7 + (6 * 2) = 19
min = 2 + (6 * 1) = 8
입력값이 8~19 사이에 있지 않음.
n++
n = 3
max = 19 + (6 * 3) = 37
min = 8 + (6 * 2) = 20
입력값이 20~37 사이에 있지 않음
n ++
n = 4
max = 37 + (6 * 4) = 61
min = 20 + (6 * 3) = 38
입력값이 38~61 사이에 있음
=> n+1 출력 ('1'출발점을 포함하기 위함)
답 : 5
댓글
댓글 쓰기