# [Silver V] 건덕이의 돌탑 [문제 링크](https://www.acmicpc.net/problem/33703) ## 문제 설명 <p>아래는 건덕이의 돌탑에 대한 설명이다.</p> <ul> <li>방석 $3$개가 있고 첫 번째 방석 위에 크기가 서로 다른 $N$개의 돌이 일렬로 쌓여있다. 돌의 크기가 클수록 아래에 쌓여있다.</li> <li>한 방석에 있는 돌 한 개를 빼서 다른 방석으로 옮길 수 있다. 건덕이는 뺀 돌을 돌이 없는 방석이나 크기가 더 큰 돌 위로만 옮길 수 있다.</li> <li>돌을 옮긴 후, 각 방석 위의 돌은 일렬로 돌의 크기가 클수록 아래에 쌓여있어야 한다.</li> </ul> <p>건덕이는 다음과 같은 방식으로 돌을 뺄 수 있다.</p> <ul> <li>건덕이는 방석 위에 돌이 $1$개만 있다면 해당 돌을 뺄 수 있다.</li> <li>돌이 $2$개 이상인 경우, 건덕이는 중간에 있는 돌도 잘 빼기 때문에 빼려는 돌이 맨 밑만 아니라면 뺄 수 있다.</li> </ul> <p>건덕이는 모든 돌을 세 번째 방석으로 옮기고 싶어 한다. 이때 필요한 돌의 최소 이동 횟수를 구해보자.</p> ## 입력 <p>첫 번째 방석 위에 쌓여있는 돌의 개수 $N$이 주어진다. $\left(1 \le N \le 100\, 000\right)$</p> ## 출력 <p>모든 돌을 세 번째 방석으로 옮기는 데 필요한 돌의 최소 이동 횟수를 출력한다.</p> ## 풀이 #### 이 문제의 목표는 세 번째 방석에 큰 돌이 아래로 가도록 쌓는 최소 횟수를 구하는 것이다. 처음에는 첫 번째 방석에만 큰 돌이 아래로 가도록 N개의 돌이 쌓여있다. #### 먼저 첫 번째 방석의 가장 무거운 돌인 가장 아래에 있는 돌을 세 번째 방석에 옮기려면 먼저 그것보다 가벼운 N-1개의 돌을 두 번째 방석으로 옮겨야 한다. 이때 두 번째 방석으로 옮기는 횟수 N-1번, 세 번째 방석으로 옮기는 횟수 1번, 총 이동 횟수는 N번이다. 이 방식으로 모든 돌을 옮기면 총 N + (N-1) + ... + 2 + 1 = N(N+1)/2 번의 이동이 필요하다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); long long n; cin >> n; cout << n*(n+1)/2; } ```