인프런 커뮤니티 질문&답변
작성한 질문수
C언어로 코드를 짜면 채점 시에 한 문제 빼고 시간 초과가 발생하는데 해결하는 방법이 있을까요?
작성
·
78
0
#include <stdio.h>
#include <stdlib.h>
int main(){
int n, res=0;
scanf("%d", &n);
int* arr = (int*)malloc(n+1);
int* dy = (int*)malloc(n+1);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
}
dy[1] = 1;
for(int i=2; i<=n; i++){
int max=0;
for(int j=i-1; j>=1; j--){
if(arr[j]<arr[i] && dy[j]>max){
max = dy[j];
}
}
dy[i] = max + 1;
if(dy[i]>res){
res = dy[i];
}
}
printf("%d\n", res);
return 0;
}이런 식으로 C로 코드를 짰습니다.
시간 초과 문제를 해결할 수 있는 방법이 있을까요?
답변 1
0
김태원
지식공유자
안녕하세요^^
배열을 동적으로 선언한 부분에서 문제가 있는 것 같습니다. 아래와 같이 선언해보세요.
int *arr = (int*)malloc(sizeof(int) * (n+1));
int *dy = (int*)malloc(sizeof(int) * (n+1));아니면 아래와 같이 해도 동적으로 됩니다.
int arr[n+1];
int dy[n+1];