글 읽기 - 문제 질문드립니다! ㅠㅠㅠ

pda_pro12 6년 전 0

어떤 문제를 풀고있는데요... 백준 온라인저지가 아닙니다!

두명이서 게임을 진행하는데 N을 정해놓고 시작합니다!

번갈아가면서 서로의 차례마다 x를 2x 또는 2x+1의 연산을 수행합니다.

x는 초기값으로 항상 1부터 시작하구요.

만약 연산결과가 N을 초과하는 순간이 왔을때 그 연산을 수행한사람이 패배하는 문제입니다.

그래서 입력으로 N하나만 주어졌을때 승자를 출력하는문제인데요(두명의 이름은 편의상 A, B로 하겠습니다. )

두사람이 최선을 다해서 게임에 임한다는 조건이 주어졌습니다(최선을다한다는 것이 어떻게 이해해야할지 몰라서 일단은 제 방식데로 아래 코드에 구현해보았습니다.)

n의 범위는 1~ 10^18까지 주어지는데요. 테스트케이스는 전부 잘돌아갑니다만 시간초과의 문제가 생겨버렸습니다....

오늘 하루종일 고민한것같은데... 너무 머리가 아파오네요... 고수님들중에 혹시 조언좀 해주실분 계신가요?"ㅠㅠㅠ

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;

long long n; long long cnt;
long long x = 1;  long long t;
int main()
{
	cin >> t;
	for (int tc = 1; tc <= t; tc++) {
		cnt = 0; x = 1;
		cin >> n;

		while (x <= n) {
			cout << cnt << " ";
			cnt++;
			long long a = 2 * x + 1;  // 내가 수행한 연산결과
			long long b = 2 * x;   

			if (a > n && b > n)    // 내가 수행한 연산결과가 n보다 크면 바로 break;
				break;

			if (a <= n) {   // a가 n보다 작거나 같을경우
				if (2 * a + 1 > n && 2 * a > n)   // a를 선택해서 상대방에게 보냈을때 상대방의 모든 연산결과가 n을 초과하는 경우(최선을 다하는 경우)
					x = a;  // 상대방에게 2x+1의 연산을해서 보낸다
				else
					x = b;   // 만약 상대방이 한턴에 Die하지 않는다면 다다음턴에 나에게로 돌아오는 수가 최대한 작아야하므로 2x의 연산을 수행해서 보낸다(최선을 다하는 경우)
			}
		}
		if (cnt % 2 == 1) {   // 홀수번의 연산수행이 이루어지고 마쳤을 경우
			cout << "B" << endl; // Bob의 승리이다
		}
		else if (cnt % 2 == 0) {  // 짝수번의 연산수행이 이루어지고 마쳤을 경우
			cout << "A" << endl; // A의 승리이다.
		}
	}
	return 0;
}

sgchoi5 6년 전 0

종만북에서 유사한 문제풀이를 본 것 같은데..... DP 관련 장이었던 듯....

댓글을 작성하려면 로그인해야 합니다.