글 읽기 - 나무 심기 틀렸습니다. 나오는데 왜 틀렸는지 잘 모르겠습니다.

inspire12 7년 전 0

DP를 통해 풀었습니다. // 그래서 시간 복잡도가 index 마지막 수 k 일 때 O(k) 입니다.

모두 저장하고 입력한 index의 값만 뽑아서 곱한 값을 출력했습니다.

mod 연산 법칙 따라 곱해서 저장했는데 계속 틀렸다고만 나와서 어떤 게 잘못 된건지 답답합니다.

#include <stdio.h>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
 
int input[200001] ={0,};
vector<int> v;
long long tree[200001]={0,};

stack<int> s;
int main(){
int n;
scanf("%d", &n);
int a;
for(int i=0; i<n; i++){
scanf("%d" ,&a);
input[a] = 1;
v.push_back(a);
}
if(n==1) {printf("%d",0); return 0;}

//sort(v.begin(),v.end());
//a = v.back();
int treeCount = 0;
for(int i=1; i<=a; i++){
tree[i] = (tree[i-1] + treeCount); 
if(input[i] == 1) treeCount++;
}
//printf("%d\n", treeCount); 
long long output = 1;
while(v.size()>1){
output = (output  % 1000000007) * (tree[v.back()] % 1000000007 );
v.pop_back();
}

printf("%lld\n", output% 1000000007);
//return 0;
}

yclock 7년 전 1

나무의 좌표는 서로 다르다는 보장이 없습니다.

만일, 나무의 좌표가 서로 같을 수 있다면, 다음과 같은 반례 데이터가 존재합니다.

/*
Input
3
1
2
1

Your Output
0

Correct Output
1
*/

inspire12 7년 전 1

감사합니다!

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

문제

문제

출처

ICPC

나무 심기 틀렸습니다. 나오는데 왜 틀렸는지 잘 모르겠습니다.

inspire12 7년 전 0

yclock 7년 전 1

inspire12 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말