bsdlcksdn   11달 전

노가다 식으로 짜서, 대충 12개정도의 배열을 선언해서

끝에서부터 1씩올리면서 조건 판단을 하는 방식으로 했는데요;

1000만넣어도 1초?2초? 정도 걸리네요...

어디서 시간초과가 나는걸까요?


그리고 N번째 감소하는 수가없을때 -1이라고 하는데

없을 수가 있나요?? 무조건 존재하지 않나요?


#include<iostream>
using namespace std;

int arr[12] = { 0, };

int main(){

int n;
int count = 9;
int index = 11;

cin >> n;

if (n < 10){
count = n;
cout << count << endl;
return 0;
}

arr[10] = 1;
arr[11] = 0;

while(1) {

//확인
int i;
for (i = 0; i <12; i++){

if (arr[i] != 0){

for (int j = i; j<= 10 ; j++){
if (arr[j] <= arr[j+1])
goto exit;
else{
continue;
}
}
count++;
break;
}
}


exit:
/*cout << "count :" << count << endl;
for (int i = 0; i < 12; i++){
cout << arr[i] << " ";
}
cout << endl;*/

//탈출~
if (n == count)
break;

//증가
arr[index]++;

for (int a = 11; a >= i; a--){
if (arr[a] >= 10){
arr[a - 1]++;
arr[a] %= 10;
}

}


}

//출력

for (int i = 0; i < 12; i++){
if (arr[i] != 0){

for (int j = i; j <= 11; j++)
cout <<arr[j];

return 0;
}
}

}

ntopia   11달 전

제일 큰 감소하는 수는 9876543210 이겠죠?

생각해보면 감소하는 수의 개수가 엄청 적다는 걸 알 수 있습니다.

bsdlcksdn   11달 전

아... 9876543210이 있네요.. ㅋㅋ 감사합니다~
혹시 시간초과의 원인은 알 수 없을까요..?
1000을 넣어도 쫌 걸리는데

N이 1000이라 쳐도, 제가 생각할때는 위에 0이아닌수를 찾는 부분에서 많아야 120?

나와서 1증가시키는곳까지 합쳐도 한 100~200사이일거 같은데

그러면 약 1000*(100~200)쯤 되지 않을까요....?

ntopia   11달 전

N이 1000이 들어왔으면

바깥쪽 while문을 1000번만 반복하는게 아니라
1000번째 감소하는 수가 나올때까지 반복하겠죠
그리고 1000번째 감소하는 수는 대략 1억에 가까우니까
당연히 시간초과가 나겠죠

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