백준 2292번 벌집 - SWIFT, C++

문제

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

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

 

출력

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

 

문제 링크

https://www.acmicpc.net/problem/2292

 

 

풀이

---

간단한 등차수열의 합 문제다.

등차수열의 합 공식을 써도 되지만, 몇번째 항 까지의 등차수열의 합인지를 아는게 핵심이라고 생각하여 합 공식을 사용하지 않고 항을 늘려가며 빼는 방식을 취했다.

 

먼저 이 방법이 왜 되는지를 알아보자.

 

위의 그림을 잘 보면 이렇게 맨 처음 블록, 1을 기준으로 층으로 구분이 가능하다. ▼

 

 

이렇게 층으로 분리된 블록들을 가장 첫 번호와 가장 뒷 번호로 정리를 해보면 각 층이 6개씩 증가함을 알 수 있다.

그러면 만약에 58번 블록에 가고 싶다고 하면, 몇 개의 층을 이동하면 되는지를 생각하면 된다.

왜냐면 층 단위로 이동하면 1번에서 어디든 갈 수 있기 때문이다.

 

그러면 아래와 같이 계산이 가능해진다. ▼

 

 

6, 12, 18, ... 으로 등차수열로 빼다 보면 어느 순간 0보다 같거나 작아지는 시점이 오게 되는데, 이렇게 되면 해당 층에 이동했다는 것과 같기에 중단하고 총 몇 개의 층을 이동했는지 확인한다.

위의 예시를 보면 4개의 층을 이동했고, 이동하면서 4개의 블록을 밟은 것인데 1번도 밟은 것이기에 총 5개의 블록을 밟았다고 볼 수 있다.

그래서 5개의 블록을 밟았다! 라고 답이 나온다.

 

Swift 코드

---

let N = Int(readLine()!)!
var count = 1
var room = 0

while true {
    room = count * count * 3 - count * 3 + 1
    if room >= N {
        print(count)
        break
    }
    count += 1
}

 

 

C++ 코드

---

#include <iostream>

using namespace std;

int N;
int cnt = 1;

int main() {
    cin >> N;

    N -= 1;
    if (N == 0) {
        cout << cnt;
    }

    while (N) {
        if (N - 6 * cnt <= 0) {
            cnt++;
            cout << cnt;
            break;
        }
        N -= (6 * cnt);
        cnt++;
    }
}