강의로 돌아가기
최웅준

수학의 조합식을 이용하여문제를 풀었습니다.

#include <string>
#include <vector>

using namespace std;
int combination(int n , int r){
    if(n==r || r==0){
        return 1;
    }else{
        return combination(n-1 ,r-1) + combination(n-1 ,r );
    }
}
int solution(int n) {
    int answer = 0;
    if (n==1) {
        answer = 1%1000000007;
        return answer;
    }
    if(n%2 == 0){
        for(int i = n/2 , int m = n/2; i<=n ;i++ , m--){
            answer = answer + combination(i,m);
        }
    }else{
        for(int i=n/2 + 1, int m = n/2 ; i <= n ; i++ ,m-- ){
            answer = answer + combination(i,m);
        }
    }
    answer = answer % 1000000007;
    return answer;
}

수학의조합식을 이용하여 문제를 풀었는데 , 0점이 나옵니다.

테스트케이스는 전부 통과했는데 왜그럴까요

3 개의 답변
Demi

올려주신 코드를 제출하니 컴파일에러가뜨는데요 ㅜㅜ.
작성한 코드가 위 코드가 맞나요?

  • 최웅준
    테스트케이스는 전부 통과햇습니다. 왜 , 0점인지 모르겟네요 최웅준 2018.08.22 11:50
  • Demi
    테스트케이스를 통과했다는게 무슨 뜻인지 모르겠어요. 제가 위 코드를 실행하면 컴파일 에러가 바로 리턴되는데요.. Demi 2018.08.22 14:05
최웅준
#include <string>
#include <vector>

using namespace std;
int combination(int n , int r){
    if(n==r || r==0){
        return 1;
    }else{
        return combination(n-1 ,r-1) + combination(n-1 ,r );
    }
}
int solution(int n) {
    int answer = 0;
    int m  = 0;
    if (n==1) {
        answer = 1;
        return answer;
    }
    if(n%2 == 0){
        for(int i = n/2 , m = n/2; i<=n ;i++ , m--){
            answer = (answer + combination(i,m))%1000000007;
        }
    }else{
        for(int i=n/2 + 1, m = n/2 ; i <= n ; i++ ,m-- ){
            answer = (answer + combination(i,m))%1000000007;
        }
    }
    return answer;
}

아.. 죄송합니다. 여행갓다와서 지금봣어요... 
코드를 다른걸 올렷네요 .. 다시한번 확인해주실레요?
Demi

프로그래머스의 정확성테스트케이스는 10초 이상이 걸리는 코드는 타임아웃으로 처리합니다.
재귀로 푸셨네요. 지금 구현하신 코드는 엄청 느린 코드라, 타임아웃에 걸릴 수 밖에 없습니다.

n = 100만 되어도 실행시간이 10초가 넘네요.
문제에 주어진 n은 최대 60,000이니, 당연히 타임아웃에 걸릴거에요.

좀 더 고민한 후 코드를 개선해보세요.

  • 최웅준
    네..답변 감사합니다. 최웅준 2018.08.28 14:44
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.