백준 18127번: 모형결정

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

18127번: 모형결정

 

 

0. 알고리즘 분류

 수학, 사칙연산

 

 

1. 문제

 지윤이는 신기한 물질을 발견했다. 이 물질의 결정은 정다각형을 유지하며 온도가 1도 낮아질 때마다 각 변을 이루는 결정의 수가 1씩 증가한다. 최초의 결정은 섭씨 0도에서 1개의 결정으로 이루어진다. 이 결정을 최소 결정이라고 하자. 결정의 크기가 증가할 때의 규칙은 다음과 같다. 그림에서 기존 결정은 파란색으로, 각 온도에서 새로 생긴 최소 결정은 노란색으로 표시하였다.

 

1. 정A각형 모양을 유지한다. 정A각형이란 정다각형의 변이 A개임을 의미한다.
2. 1도 낮아질 때 각 변을 이루는 최소 결정의 수가 1씩 증가한다.
3. 최대한 적은 개수의 최소 결정들이 기존 결정에 붙는다.

 지윤이는 온도를 내려보지 않고도 해당 온도의 결정을 이루는 최소 결정의 개수를 알고 싶다. 지윤이를 도와 최소 결정의 개수를 출력해주는 프로그램을 작성해보자.

 

 

2. 풀이

 처음 보면 쉬울 수 있다. 규칙이 대놓고 나와있으니 그렇게 보인다. 하지만, 이 문제에서 규칙에 사용되는 변수는 2가지이다. 변의 수 A와 온도 B이다. 수식 쓰기 귀찮으니까 수식 설명은 안한다. 점화식을 이용하면 상상이상으로 코드가 간단하다. 반복문을 이용해서 풀 수도 있지만, 대다수의 사람들이 0ms로 규칙을 수식화시켜서 풀었으니 노력해보자.

 

 

3. 코드

#include <iostream>

using namespace std;

int main(void) {
    long long a, b;
    cin >> a >> b;
    cout << (a-2)*b*(b+1)/2 + b + 1;
    
    return 0;
}