https://www.acmicpc.net/problem/2292
중앙(1)부터 시작해 시계방향으로 돌아가며 1씩 증가하는 벌집이 있다. 입력받은 숫자의 방까지 도달하고자 할 때 최소 개수의 방을 구하는 문제이다.
벌집은 육각형으로 이루어져 있으므로, 둘러싸는 벽의 개수도 6의 배수만큼 늘어난다.
1을 둘러싸는 벽은 6개, 그 벽을 둘러싸는 벽은 12개.
이 규칙을 이용하면 된다.
#include <iostream>
#include <string>
using namespace std;
int main(){
// 벌집은 육각형으로 이루어져 있음.
// 그러므로, 둘러싸는 겉의 벽의 개수가 6의 배수.
// ex. 1을 둘러싸는 벽의 개수는 6개. 2~7
// 위의 6개의 벽을 둘러싸는 벽의 개수는 12개. 8~19
// 반복문을 돌며 6, 12, 18... 을 입력 받은 수에서 뺐을 때 1이하가 될 경우, 반복한 횟수가 정답이 됨.
int n;
cin >> n;
int i = 1;
while(n > 1){
n -= (i * 6);
i++;
}
cout << i;
}
i번의 횟수만큼 6의 배수를 증가시키며 뺄셈을 하다보면 1 이하가 되는 때가 온다. 이 때, i번이 곧 목적지까지의 최소 개수의 방을 의미한다.
'알고리즘 > 백준' 카테고리의 다른 글
백준 2869번 달팽이는 올라가고 싶다 [C++] (1) | 2023.11.26 |
---|---|
백준 1193번 분수찾기 [C++] (0) | 2023.11.26 |
백준 2903번 중앙 이동 알고리즘 [C++] (1) | 2023.11.26 |
백준 2720번 세탁소 사장 동혁 [C++] (1) | 2023.11.26 |
백준 11005 진법 변환 2 [C++] (0) | 2023.11.26 |