1일차

2020-09-02

초급 : 19575 Polynomial (Bronze I)

www.acmicpc.net/problem/19575

19575번: Polynomial

 

#include <bits/stdc++.h>
using namespace std;

long long N, x, a, b, r = 0;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> x;

	while (N-- >= 0) {
		cin >> a >> b;
		r *= x;
		r += a;
		r %= 1000000007;
	}

	cout << r;

	return 0;
}

 

다항식의 차수 N, 평가할 값 x를 입력받는다.

2x²+3x+5 = x(2x+3)+5 처럼 상수항을 빼고, 공통 인수로 묶는 것을 반복하여 만들어진 식을 계산하면 된다.

 

function = 2x²+3x+5, x = 6 일 때 입력은 다음과 같다.

 

2 6
2 2
3 1
5 0

 

반복문을 확인해보면 다음과 같은 순서로 계산이 이루어짐을 관찰할 수 있다.

 

r	function	r *= x	r += a
2	x(2x+3)+5	0	2
15	x(2x+3)+5	12	15
95	x(2x+3)+5	90	95

2x²+3x+5 에 6을 대입해 보면 같은 결과를 얻을 수 있다.

 

수학을 잘 못해서 이해하는데 굉장히 오래 걸렸다.

 

 

중급 : 13699 점화식 (Silver IV)

www.acmicpc.net/problem/13699

13699번: 점화식

 

#include <bits/stdc++.h>
using namespace std;

int n;
long long dp[36];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    dp[0] = 1;
    cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }

    cout << dp[n];

    return 0;
}

 

수열 T_n이 T0 = 1, Tn = T₀*T_n-1+T₁*T_n-2+...+T_n-1*T₀ 으로 정의된다고 한다.

dp 배열을 0으로 초기화 하고, dp0에 1을 넣는다.

 

dp₁부터 dp_n까지 iterate 하며 위 점화식에 따라 값을 계산하면 된다.

T_i는 T₀ * T_i-1 + T₁ * T_i-2 + ... + T_i-1 * T₀ 이 될 것이다.

 

 

고급 : 9660 돌 게임 6 (Gold V)

www.acmicpc.net/problem/9660

9660번: 돌 게임 6

 

print("CY" if abs(int(input())%7-1)==1 else "SK")

 

N	1	2	3	4	5	6	7
승자	상근	창영	상근	상근	상근	상근	창영

N = 7 까지의 승자를 나열하면 위 표와 같다.

 

N = 1 일 때, 돌 하나를 가져가면 상근이가 이긴다.

N = 2 일 때, 상근이는 돌을 하나만 가져갈 수 있다. 남은 돌을 가져가는 창영이가 이긴다.

N = 3 | 4일 때, 돌을 3개, 4개 가져가면 상근이가 이긴다.

N = 5 일 때, 상근이가 돌을 2개 남기면 창영이는 돌을 하나만 가져갈 수 있다. 남은 돌을 가져가는 상근이가 이긴다.

N = 6 일 때, 상근이가 돌을 4개 가져가면 위와 같은 상황이 벌어져 상근이가 이긴다.

N = 7 일 때, 상근이가 돌을 어떻게 가져가도 창영이가 이긴다.

 

 

N = 7 일 때 상근이가 이길 수 없는 이유는 무엇일까?

 

N = x 일 때 승자가 A라면, 이전에 돌 x개를 남기고 턴을 마친 B는 패배한다.

N = 7 일 때를 다시 보면 상근이가 돌을 어떻게 가져가도 다음 턴에 자신이 돌을 한번 더 가져가야 승리할 수 있다.

이는 번갈아가면서 돌을 가져간다는 문제의 조건에 모순된다.

 

따라서 N = 7 일 때 상근이는 승자가 될 수 없다.

 

이 논리로 N을 확장해가며 승자를 구하면 7을 주기로 [상근 창영 상근 상근 상근 상근 창영] 이 반복된다.

따라서 N % 7이 0, 2일 때 창영이가 이기고 나머지는 상근이가 이긴다.