글 읽기 - 반례를 모르겠습니다!

idjjm95 3년 전 0

안녕하세요.

백준 문제를 풀고있는데 잘 해결이 안됩니다.

이분탐색을 활용해서 코딩을 했습니다

그래서 예제에 나오는 코드까지는 맞다고 나오는데

계속 4%에서 틀렸다고 나옵니다.

혹시 반례가 무엇이 있을까요?

#include<cstdio>
#include<algorithm>
#include<climits>
#include<iostream>

using namespace std;

long long int HMAX = LLONG_MAX; // 최대 생명력 
long long int HCur; //현재 용사의 생명력 
long long int HATK; // 용사의 공격력 
int N;

int monster[123456][3];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	long long int first=1;
	long long int HATK_cha; // 주인공의 증감되는 공격력 
	cin >> N;
	cin >> HATK; //원래 공격력 

	long long int MID;
	long long int HP_cha; //주인공의 남은 HP
	bool flag_mon; //몬스터의 생존 
	bool flag_cha; //캐릭터의 생존 
	for(int i = 0; i < N; i++)
		for(int j = 0; j<3; j++)
			cin >> monster[i][j]; // 몬스터 정보입력
			
	
	while(first <= HMAX)
	{
		MID = (first+HMAX)/2;
		flag_mon = true; //monster 생존 
		flag_cha = true; //주인공 생존 
		HATK_cha = HATK; //공격력 초기화 
		HP_cha = MID;
		
		for(int i=0; i<N ;i++)
		{
			flag_mon = true;
			if(monster[i][0]==1)
				if(((HP_cha-1)/monster[i][1]) >= ((monster[i][2])-1)/HATK_cha)
				{
					HP_cha = HP_cha - ((monster[i][2]-1)/HATK_cha) * monster[i][1];
					flag_mon = false;
				}
				else{
					flag_cha = false;
					break;
				}
			//flag_mon = true;
/*			if(monster[i][0]==1)
			{
				flag_mon = true;
				HP_mon = monster[i][2];
				HP_mon = HP_mon - HATK_cha;
				if((HP_mon/HATK_cha)==(HP_cha/monster[i][1])){ //경우의 수 3가지 나머지가 둘다 0, 주인공이 나머지가 0인 부분이 가장 애매 
					if((HP_cha % monster[i][1]) == 0) // mon
						if((HP_mon%HATK_cha) == 0) // 나머지가 둘 다 0 -> 주인공이 이김 
						{
							HP_cha = HP_cha - (	( (HP_mon/HATK_cha) -1) * monster[i][1]);
							flag_mon = false;
							cout << "1: HP_cha = " << HP_cha <<" i = " << i <<"\n";
							continue;
						}
						else{ //주인공만 나머지가 0인 부분  -> 몬스터가 이김 
							flag_cha = false;
							cout << "2: HP_cha = " << HP_cha <<" i = " << i <<"\n";
							break;
						} 
				}
				else if((HP_mon/HATK_cha)>(HP_cha/monster[i][1])){ //몬스터가 더 쎔  -> 체력 올려야됨 
					flag_cha=false;
					break;
				}
				else// if ((HP_mon/HATK_cha)<(HP_cha/monster[i][1])) //몬스터가 더 약함 -> 체력 깍는다. 
				{
					if((HP_mon%HATK_cha) == 0) // 나머지가 둘 다 0 -> 주인공이 이김 			
						HP_cha = HP_cha - (	( (HP_mon/HATK_cha) -1) * monster[i][1]);
					
					else
						HP_cha = HP_cha - (	( (HP_mon/HATK_cha)  ) * monster[i][1]);
					flag_mon = false;
					cout << "3: HP_cha = " << HP_cha <<" i = " << i <<"\n";
					continue;
				}
*/				
/*				
	while(flag_mon && flag_cha)
				{
					HP_mon -= HATK_cha; //1. 용사의 공격력만큼 몬스터의 생명력을 깎는다.
					if(HP_mon <= 0) { flag_mon = false; break;} //2. 몬스터의 생명이 2이하이면 전투가 종료되고 다음 방으로 간다. 
					HP_cha -= monster[i][1]; //3.몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
					if(HP_cha <= 0){ flag_cha = false; break;} //4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
				//	cout << "MID = " << MID << "n = "<< i <<"\n";
				}
*/			
			else
			{
				HATK_cha += monster[i][1]; //공격력 증가 
				HP_cha = HP_cha + monster[i][2]; //체력 증가 
				HP_cha = min(MID, HP_cha); //한도 이상이면 체력을 MID로 맞춘다. 
			}
			//if(!flag_cha) break; //캐릭터가 죽으면 다시 해야됨 
			
		}
		if(!flag_cha) first = MID+1;
		else if(flag_cha) HMAX = MID-1;
		
	//	cout << "first = " << first <<"\n";
	//	cout << "HMAX = " << HMAX <<"\n";
		
	
	} 
	
	cout << first << "\n";
	
	return 0;
}

htjung09 2년 전 0

HMAX를 LLONG_MAX로 해버리면 MID 구하는 부분에서 left + right 할 때 오버플로우 때문에 값이 잘 나오지 않습니다.

long long int 부분을 모두 unsigned long long int로 하거나 HMAX를 적당하게 큰 값으로 해보세요!

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

문제

문제

출처

ICPC

반례를 모르겠습니다!

idjjm95 3년 전 0

htjung09 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말