처음 쓰는 velog #1
출처 : https://www.acmicpc.net/problem/2292
문제 풀다가 '틀렸습니다' 7번에 '컴파일 에러' 2번 났다.ㅠㅠ
어제 밤에 풀다가 덮고 아침에 그림 새로 그렸더니 식을 도출했다.
아유 그림이 화면 가득하게 나오네
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.
말로 하는 설명
위 그림을 보면 1에서부터 아래로 1 증가, 그 다음은 1을 중심으로 시계방향 원을 그리며 1을 감싸고 돈다.
7까지 첫번째 원 완성. 그 다음은 7에서 아래로 1칸 이동해서 또 시계방향 원을 그리며 첫번째 원을 감싸고 도는 두번째 원 완성.
숫자가 1씩 증가해 원이 완전해지는 지점을 살펴보면 1, 7, 19, 37, 61 이렇게 커지는데. 1부터 +6, +12, +18, +24 가 되는 것을 알 수 있다. 즉 6의 배수만큼 커지면서 원을 새로 생성한다. 애초에 벌집이 육각형인것에서부터 눈치를 챘어야 했나 암튼
1, 7, 19, 37, 61... 을 식으로 표현해본다면
1, 1+(6x1) , 1+(6x1+6x2), 1+(6x1+6x2+6x3), 1+(6x1+6x2+6x3+6x4) 요런 식으로 표현할 수 있다.
1+(6x1+6x2+6x3+6x4) 요걸 떼어와서 일반식으로 표현해보면 1+6(1+2+3+4) 가 된다.
1부터 n까지 더하는 공식은 n(n+1)/2 이므로 1+6(1+2+3+4) = 1+6x{4x(4+1)/2} = 61
결국 1, 7, 19, 37, 61... <- 요건 3n(n+1)+1 로 표현할 수 있다.
여기까지 이해가 된다면 바로 코드로 >>
이해가 안됐어요? 괜찮아요
1은 뭐 시작한 방이니까 1개일거고(시작한 방까지 포함해서 센다) 7보다 작거나 같은 숫자라면 1번 방 외에 한칸 더 움직여야 그 방으로 이동할 수 있으므로 2개의 방을 지나간다.
19보다 작거나 같은 숫자라면, 1을 둘러싼 2번째 원이므로 1 외에 두 칸을 더 움직여야 해당하는 숫자의 방으로 이동할 수 있다. 1+2 = 3개의 방을 지나가야 한다는 말
19는 1+(6x1+6x2+6x3) -> 3n(n+1)+1 여기서 n에 2를 대입한 값이고, 1을 포함하여 3개의 방을 지나야 도달할 수 있는 곳!
7보다 크고 19보다 같거나 작다면 3개의 방을 이동해야 한다. 따라서 n+1 개의 방을 이동하면 된다.
아래에 요 식을 그대로 쓴 코드가 있다.
코드(C++)
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int a;
cin >> a;
for (int i = 0;; i++)
{
if (a <= 3 * i * (i + 1) + 1)
{
cout << i + 1;
return 0;
}
}
}
성공이얌