글 읽기 - 풀이가 틀렸나요...

cocogod 7년 전 0

재귀로 n 번 돌립니다.

이때 그전수보다 2배 커야하니까 for문에 초기값을 2배 크게하였습니다.

그후 하나씩 재귀호출을 합니다.

이때 메모라이징하여 다음에 찾을것을 저장하였습니다.

틀렸다고 뜨는데 잘못 짠건가요.. ㅠㅠ

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int n,m;
long long dp[11][2001];

long long test(int num,int turn){
    
    if(turn == n) return 1;
    
    long long &ans = dp[turn][num];
    if(ans != -1) return ans;
    
    ans = 0;
    
    
    for(int i=num*2;i<=m;i++){
        if(i ==0)
            i= 1;
        ans += test(i,turn+1);
    }
    return ans ;
}

int main(){
    int t;
    cin >> t;
    
    for(int i=1;i<=t;i++){
        
        memset(dp,-1,sizeof(dp));
        cin >> n >> m;
        printf("%d %lld\n",i,test(0,0));
    }
}

zlzmsrhak 7년 전 0

답을 계산한 뒤에 dp 배열을 -1로 초기화시켜야 할 것 같습니다.

cocogod 7년 전 0

@zlzmsrhak 이제 틀리지않고 시간초과 가 뜹니다 ㅠㅠ ...

메모라이징 잘한거 같은대 아닌가요?

zlzmsrhak 7년 전 2

음.. 생각보다 테스트케이스가 많았나 보네요.

모든 (n, m) 쌍에 대하여 답을 O(10 * 1000) 으로 구해야만 시간초과가 나지 않을 것 같습니다.

예를 들면, dp[n][m] = (숫자가 n개, 숫자 제한이 m일 때의 답)으로 정의하면 됩니다.

지금 dp table의 값은 m이 바뀌면 바뀌기 때문에 식을 수정해야 합니다.

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

문제

문제

출처

ICPC

풀이가 틀렸나요...

cocogod 7년 전 0

zlzmsrhak 7년 전 0

cocogod 7년 전 0

zlzmsrhak 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말