백준 14679번: 영우와 '갓4'

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

14679번: 영우와 ‘갓4’

---

$N$이 매우 크지만, 풀이는 생각보다 단순한 문제입니다.

 

우선 가장 나이브하게 $O(N(A_{p}+D_{p}+H_{p}))$ 또는 $O(N\log(A_{p}D_{p}H_{p}))$으로 매번 몬스터의 공격력, 방어력, 체력을 시뮬레이션하는 것은 시간제한을 통과할 수 없어보입니다.

 

그런데 어차피 $A_{k} \; D_{k} \; H_{k}$는 각각 1부터 100, 1부터 3, 1부터 1000 사이의 값을 가지므로, 몬스터의 공격력, 방어력, 최대 체력을 각각 functional graph로 모델링할 수 있습니다. 그러므로 반드시 cycle이 존재할 것이고, 이제 몬스터의 cycle의 시작점과 cycle의 크기를 잘 찾아서 풀어주면 될 것 같아보이지만...

 

Cycle을 찾지 않아도 $O(N)$으로 통과할 수 있도록 되어 있습니다. 배열에 각 정점에서 출발하여 도착하는 정점을 저장하면, 공격력, 방어력, 체력을 $O(1)$에 구할 수 있기 때문입니다. 제 코드는 다음과 같습니다.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define mod 1000000007

long long power_modular (long long X, long long Y, long long M);

long long A, D, H;
long long MA, MD, MH;
long long Ap, Aa, Dp, Da, Hp, Ha;
long long Monster_Attack_After_[101];
long long Monster_Defense_After_[4];
long long Monster_MaxHealth_After_[1001];

long long max (long long A, long long B);

void Absorb (void);
void Call_Next_Monster (void);
void Battle (void);

int main() {

	int N;
	scanf("%lld", &N);
	scanf("%lld %lld %lld", &A, &D, &H);
	scanf("%lld %lld %lld", &MA, &MD, &MH);
	scanf("%lld %lld %lld %lld %lld %lld", &Ap, &Aa, &Dp, &Da, &Hp, &Ha);
	
	for (int i = 1; i <= 100; i++) {
		Monster_Attack_After_[i] = 1 + (power_modular(i, Ap, 100) + Aa) % 100;
	}
	for (int i = 1; i <= 3; i++) {
		Monster_Defense_After_[i] = 1 + (power_modular(i, Dp, 3) + Da) % 3;
	}
	for (int i = 1; i <= 1000; i++) {
		Monster_MaxHealth_After_[i] = 1 + (power_modular(i, Hp, 1000) + Ha) % 1000;
	}
	
	for (int i = 0; i < N; i++) {
        Battle();
	}
    
	printf("%lld %lld %lld", A % mod, D % mod, H % mod);
	return 0;
}

long long power_modular (long long X, long long Y, long long M) {
	long long result = 1;
	while(Y) {
		if (Y % 2) {
			result = result * X % M;
		}
		X = X * X % M;
		Y /= 2;
	}
	return result;
}

long long max (long long A, long long B) {
	return A > B ? A : B;
}

void Absorb (void) {
	A += MA;
	D += MD;
	H += MH;
}

void Call_Next_Monster (void) {
	MA = Monster_Attack_After_[MA];
	MD = Monster_Defense_After_[MD];
	MH = Monster_MaxHealth_After_[MH];
}

void Battle (void) {
	long long damage_to_monster = max(A - MD, 1);
	long long turns_to_kill_monster = (long long)ceil((double)MH / damage_to_monster);
	
	long long damage_to_player = max(MA - D, 1);
	long long turns_to_kill_player = (long long)ceil((double)H / damage_to_player);
	
	if (turns_to_kill_player < turns_to_kill_monster) {
        printf("-1");
        exit(0);
	}
	else {
		Absorb();
		Call_Next_Monster();
	}
}

(C11, 388ms, 1124KB, 제출번호 55310890)

---