백준 17845 수강 과목

문제 URL : https://www.acmicpc.net/problem/17845

17845번: 수강 과목

 

문제 접근법:

배낭문제이지만 dfs+메모이제이션으로 활용해서 풀수있는문제입니다.

메모리는 10000*1000 이라 1천만까지는 괜찮기때문에 

 

메모이제이션이 c++에선 가능하지만

똑같이 코딩했는데 python에서 시간초과가 나더군요 

파이썬은 dfs + 메모이제이션이 힘든것같습니다.

 

처음에 파이썬으로 풀어서 시간초과 나길래 어딜 개선해야되나 싶었는데 찾질못해서 그냥 c++로 풀었더니

c++은 되고 파이썬은 안되고 참 의아했습니다.

 

소스코드:

#include <bits/stdc++.h>
using namespace std;
int n,k;
int dp[10001][1001];
vector<pair<int,int>> v;
void input(){
	cin>>n>>k;
	int a,b;
	for(int i=0;i<k;i++){
		cin>>a>>b;
		v.push_back({a,b});
	}
}
int dfs(int sum=n,int cur=0){
	if(cur>=k)return 0;
	int &cache = dp[sum][cur];
	if(cache!=-1)return cache;
	if(sum>=v[cur].second)
		cache = max(cache,dfs(sum-v[cur].second,cur+1)+v[cur].first);
	return cache = max(cache,dfs(sum,cur+1));
}
void solve(){
	memset(dp,-1,sizeof(dp));
	cout<<dfs()<<"\n";	
}
int main ()
{	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	input();
	solve();
}

 

파이썬 시간초과코드

import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
n,k = map(int,input().rstrip().rsplit())
l = [list(map(int,input().rstrip().rsplit())) for i in range(k)]
dp = [[-1 for i in range(k)] for j in range(n+1)]
def dfs(time, cur):
    global k,l,dp
    if time <= 0 or cur>=k :return 0
    if dp[time][cur] != -1 :return dp[time][cur]

    if time>= l[cur][1]:
        dp[time][cur] = max(dp[time][cur],dfs(time-l[cur][1],cur+1)+l[cur][0])
    dp[time][cur] = max(dp[time][cur],dfs(time,cur+1))
    return dp[time][cur]
print(dfs(n,0))

두코드 차이가 없을정도로 똑같은데?

컴파일언어가 인터프리터 보다는 빠르다는 것은 알고있었지만

알고리즘 문제를 풀다보면 그렇게 차이가 안나는 것처럼 보였는데

여기서 그차이를 느끼게 되네요

 

궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.