글 읽기 - 토너먼트... 시간초과가 나온는데...

mimmyum 7년 전 1

계속 반으로 줄여나가니깐 시간복잡도는 log(2)N 아닌가요...?

근데도 이렇게 시간초과가 나오다니.. 제가 중간에 뭔가 무한시키는게 있나요?

비쥬얼에서는 잘 돌아가고 있습니다.. ㅠ.ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void printTonament(int tonament);

int main() {
	int N = 100001, K=100001, H=100001;
	int tonament=1;
	int met = 0;
	
	while (N > 100000 || N < 1)
		scanf("%d", &N);
	while (K > N || K < 1)
		scanf("%d", &K);
	while (H > N || H < 1 || K == N)
		scanf("%d", &H);

	while (met != 1) {
		
			/* 이 밑으로 복사*/
			if (H % 2 == 1 && K - H == 1) {
				printTonament(tonament);
				met = 1;
				break;
			}
			else if (K % 2 == 1 && H - K == 1) {
				printTonament(tonament);
				met = 1;
				break;
			}
			else if (N == 1)
				break;

				N = (N + 1) / 2;
		
				H = (H + 1) / 2;
			
				K = (K + 1) / 2;
			
			tonament++;

			

		}
	if (N == 1 && met == 0 )
		printf("-1");

	return 0;
}

void printTonament(int tonament) {
	printf("%d", tonament);
}

crasy111 7년 전 2

때인덱스트리 아시나요?

인덱스트리에서 리프노드중 두개가 만날때 까지의 거리를 제는 문제입니다.

따라서 -1이 나올 경우는 없습니다.

그리고 3번째 수를 입력받으실때

while (H > N || H < 1 || K == N)
scanf("%d", &H);

로 하셨는데, K가 N인 경우도 있습니다. 당연하게도.

왜냐하면 K<H라는 조건이 없기때문이죠.

그래서 K==N이라는 조건을 지우셔야합니다.

mimmyum 7년 전 0

아.. 감사합니다...

저 조건에서 N은 총 사람 수고, K와 H가 사람이라서

K != H 임을 확인하기 위해 넣은 식인데

K==N으로 되어있었네요... 감사합니다.

간단한 실수인데 확인하지 못했네요.

조언 감사드립니다.

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

문제

문제

출처

ICPC

토너먼트... 시간초과가 나온는데...

mimmyum 7년 전 1

crasy111 7년 전 2

mimmyum 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말