글 읽기 - 시간초과 해결방법좀 알려주세요 ㅠㅠ

prinn9 3년 전 0

답은 맞게 나오는데 시간초과가 문제입니다 ㅠㅠ

dfs로 탐색하면서 가망없는 루트는 일찌감치 탐색 중단하고 다른 길로 찾도록해서

최대한 시간을 줄인거같은데도 계속 시간초과가 나오네요ㅠㅠ

dfs로 푸는거 자체가 틀린거같은데

어떻게 풀어야할지 힌트라도 있을까요? ㅠㅠ

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

#pragma warning(disable:4996);


int move[2] = { -1,1 };
int k, n;
int c = 0;
int total = 0;

void dfs(int index) {
	if (index == n) return;

	for (int i = 0; i < 2; i++) {
		total += move[i];
		if ( -1 * total > index + 1) { // 나머지 시간을 전부다 위로 올라가도 수면 밑인 경우(더 이상 탐색x)
			total -= move[i]; 
			return;
		}
		if (total >= k) { // 수면에 닿은 경우(더이상 탐색 x)
			c += 1 << n - index -1;
			total -= move[i];
			return;
		}
		else {
			dfs(index + 1);
			total -= move[i];
		}
	}
}

int main() {
	scanf("%d %d", &k,&n);

	dfs(0);
	printf("%d", (1<<n) - c);
}

djm03178 3년 전 0

가장 기초적으로 드릴 수 있는 힌트는 dp를 사용하라는 것입니다.

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

문제

문제

출처

ICPC

시간초과 해결방법좀 알려주세요 ㅠㅠ

prinn9 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말