글 읽기 - DP로 풀었는데 시간초과 났네요

lovingycs92 4년 전 1

n부터 1까지 되는 경우를 dp로 풀어서 접근을 했는데요

문제는 시간초과에 걸렸다는 겁니다. ㅠ.ㅠ

( 첨부한 소스코드 )

#include int Dp[1000001];

int min(int a, int b) { return a > b ? b : a; }

int main(void) {

int N; scanf_s("%d", &N);

Dp[1] = 0;

for (int i = 2; i <= N; i++)

{ Dp[i] = Dp[i - 1] + 1;

if (i % 2 == 0) Dp[i] = min(Dp[i], Dp[i / 2] + 1);

if (i % 3 == 0) Dp[i] = min(Dp[i], Dp[i / 3] + 1);

}

printf_s("%d\n", Dp[N]);

return 0;

}

정말 궁금한것이 배열을 세워 이렇게 1부터 n까지 거꾸로 올라가니까 시간초과 문제 없이 정답이라구 뜨더라구요

둘의 차이점이 먼지 궁금합니다. 시간복잡도와 공간복잡도 측면에서 차이가 어떤 차이가 있는지

알려주시면 큰 도움이 될거 같습니다.

감사합니다.

#include<iostream>

using namespace std;

int result = 100000;

void dp(int num, int op) {
	if (num == 1) {

		if (op < result)
			result = op;   // num 이 1이 될 경우 최솟값 출력 
		return;
		 
	}

	if (num % 2 == 0) {
	  dp(num / 2, op + 1);   // 2로 나눠질경우 dp
	
	}
	if (num % 3 == 0) {
		dp(num / 3, op + 1); // 3로 나눠질 경우 dp
		
	}

	dp(num -1, op + 1);

}

int main() {
	
	 int n;
	cin >> n;

	dp(n, 0);

	cout << result << '\n';

	return 0;
}

1207koo 4년 전 1

우선 위의 코드는 모든 수를 한 번씩만 계산하기 때문에 O(n)입니다.

문제는 아래 코드에서는 DP로 돌아가지 않습니다.

예를 들면 36인 경우 2로 나누고 3으로 나눈 것과 3으로 나누고 2로 나눈 것 모두 6으로 가지만 똑같이 계산하게 됩니다.

브루트 포스 코드라고 볼 수 있는 겁니다.

djm03178 4년 전 0

실제로 dp 함수가 호출되는 과정을 그려보시면 쉽게 알 수 있습니다. 똑같은 값에 대한 함수 호출이 여러 번 이루어지고 그 때마다 재계산을 하기 때문에 문제가 됩니다.

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

문제

문제

출처

ICPC

DP로 풀었는데 시간초과 났네요

lovingycs92 4년 전 1

1207koo 4년 전 1

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말