Algorithm/λ¬Έμ œν’€μ΄

[λ°±μ€€] 9658번 - 돌 κ²Œμž„ 4 (C++)

moaoh 2023. 7. 13. 00:13

문제

돌 κ²Œμž„μ€ 두 λͺ…μ΄μ„œ μ¦κΈ°λŠ” μž¬λ°ŒλŠ” κ²Œμž„μ΄λ‹€.

νƒμž μœ„μ— 돌 Nκ°œκ°€ μžˆλ‹€. 상근이와 μ°½μ˜μ΄λŠ” 턴을 λ²ˆκ°ˆμ•„κ°€λ©΄μ„œ λŒμ„ κ°€μ Έκ°€λ©°, λŒμ€ 1개, 3개 λ˜λŠ” 4개 κ°€μ Έκ°ˆ 수 μžˆλ‹€. λ§ˆμ§€λ§‰ λŒμ„ κ°€μ Έκ°€λŠ” μ‚¬λžŒμ΄ κ²Œμž„μ„ μ§€κ²Œ λœλ‹€.

두 μ‚¬λžŒμ΄ μ™„λ²½ν•˜κ²Œ κ²Œμž„μ„ ν–ˆμ„ λ•Œ, μ΄κΈ°λŠ” μ‚¬λžŒμ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€. κ²Œμž„은 상근이가 λ¨Όμ € μ‹œμž‘ν•œλ‹€.


μž…λ ₯

첫째 쀄에 N이 μ£Όμ–΄μ§„λ‹€. (1 ≤ N ≤ 1000)


좜λ ₯

상근이가 κ²Œμž„μ„ 이기면 SKλ₯Ό, μ°½μ˜μ΄κ°€ κ²Œμž„μ„ 이기면 CY을 좜λ ₯ν•œλ‹€.


예제 μž…λ ₯ 1 λ³΅μ‚¬

6

예제 좜λ ₯ 1 λ³΅μ‚¬

SK

풀이과정

 

[λ°±μ€€] 9657번 - 돌 κ²Œμž„ 3 (C++)

문제 돌 κ²Œμž„μ€ 두 λͺ…μ΄μ„œ μ¦κΈ°λŠ” μž¬λ°ŒλŠ” κ²Œμž„μ΄λ‹€. νƒμž μœ„μ— 돌 Nκ°œκ°€ μžˆλ‹€. 상근이와 μ°½μ˜μ΄λŠ” 턴을 λ²ˆκ°ˆμ•„κ°€λ©΄μ„œ λŒμ„ κ°€μ Έκ°€λ©°, λŒμ€ 1개, 3개 λ˜λŠ” 4개 κ°€μ Έκ°ˆ 수 μžˆλ‹€. λ§ˆμ§€λ§‰ λŒμ„ κ°€μ Έκ°€

jun-13.tistory.com

이전에 풀이λ₯Ό μž‘μ„±ν–ˆλ˜ 돌 κ²Œμž„ 3κ³Ό 전체적인 λ‘œμ§μ€ λ˜‘κ°™μ§€λ§Œ 돌 κ²Œμž„ 4의 κ²½μš°μ—λŠ” 문제의 쑰건이

"λ§ˆμ§€λ§‰ λŒμ„ κ°€μ Έκ°€λŠ” μ‚¬λžŒμ΄ κ²Œμž„μ„ μ§€κ²Œ λœλ‹€."라고 쑰건이 λ°”λ€Œμ–΄μ„œ

돌 1개 2개 3개 4개
승자 CK SK CK SK

dp에 λ‹΄κΈ°λŠ” 승자의 κ°’λ§Œ λ°”κΎΈμ–΄μ£Όκ³  for문의 쑰건문만 μ•½κ°„ μˆ˜μ •μ„ ν•˜μ˜€μŠ΅λ‹ˆλ‹€.

code

#include <iostream>

int		dp[1001];

// sk = 1, ck = 0
void	stone(int n)
{
	dp[1] = 0;
	dp[2] = 1;
	dp[3] = 0;
	dp[4] = 1;
	for (int i = 5; i <= n; i++) {
		if (dp[i - 1] == 0 || dp[i - 3] == 0 || dp[i - 4] == 0)
			dp[i] = 1;
		else dp[i] = 0;
	}
}

int		main()
{
	int n;
	std::cin >> n;
	stone(n);
	if (dp[n] == 1) std::cout << "SK";
	else std::cout << "CY";

	return (0);
}


ν›„κΈ°

λŒκ²Œμž„3의 쑰건문만 λ°”κΏ€ 쀄 μ•Œλ©΄ λ˜λŠ” λ¬Έμ œμ˜€μ–΄μ„œ 돌 κ²Œμž„ 3만큼 크게 μ–΄λ ΅μ§€λŠ” μ•Šμ•˜λ˜ κ±° κ°™λ‹€.