본문 바로가기
X/인알그 스터디

1일차

by 유시은 2020. 9. 5.

2020-09-02

초급 : 19575 Polynomial (Bronze I)

www.acmicpc.net/problem/19575

 

19575번: Polynomial

경근이는 수학을 좋아한다. 수학을 너무 좋아하는 나머지 다항식을 빠르게 평가하는 프로그램을 작성했다. 미지수 x로 구성된 다항식 f(x)에서 x에 k를 대입하여 f(k)를 구하는 것을 평가라고 한다

www.acmicpc.net

 

#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를 입력받는다.

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

 

function = 2x2+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

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

 

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

 

 

중급 : 13699 점화식 (Silver IV)

www.acmicpc.net/problem/13699

 

13699번: 점화식

다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n�

www.acmicpc.net

 

#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;
}

 

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

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

 

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

Ti는 T0 * Ti-1 + T1 * Ti-2 + ... + Ti-1 * T0 이 될 것이다.

 

 

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

www.acmicpc.net/problem/9660

 

9660번: 돌 게임 6

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

www.acmicpc.net

 

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일 때 창영이가 이기고 나머지는 상근이가 이긴다.

 

'X > 인알그 스터디' 카테고리의 다른 글

6일차  (0) 2020.09.15
5일차  (0) 2020.09.15
4일차  (0) 2020.09.15
3일차  (0) 2020.09.15
2일차  (0) 2020.09.05

댓글