글 읽기 - DDR 문제 O(n^2)풀이 시간초과 질문드립니다.

imno1234 5년 전 0

DDR 문제에서 계속 시간초과가 떠서 질문드립니다.

매 입력마다 두 발 중 한 발은 마지막으로 입력된 버튼을 밟아야한다는 점에 착안하여

d[i]=해당 n번째 턴에서 n번째 버튼을 밟은 발의 반대발 이 i번째 버튼에 머물러있을 때의 점수

로 두고 입력마다 d[i]를 갱신하였습니다. 시간 복잡도 O(n^2)에 메모리비용 적은 바텀업 방식 풀이라고, 좋다고 제출하였는데 계속 시간초과가 떠서 질문드립니다.

(물론, 제가 입력해본 예제 값들은 올바른 결과를 잘 보여주었습니다.)

제가 보는 책에서는 일반적으로 수 초에 10^8번 연산 가능하다고 보던데, 이 문제의 경우 O(n^2)풀이는 최대 100,000^2=10^10번의 연산~수백초 가 걸려서 시간초과가 뜨는것인지, 아니면 제가 잡아내지 못한 실수가 있는지 궁금합니다.

#include<stdio,h>
int n,a[100005],d[100005]={0};
int m(int x,int y){return x>y?y:x;}
//minimum함수입니다.
int S(int k,int j){return k?a[j]-a[k]?a[j]%2-a[k]%2?3:4:1:2;}
//k번째로 입력된 버튼에서 j번째 버튼으로 발을 옮길때 드는 비용 함수입니다.
int main(){
	int i,f;
	for(d[0]=2,n=1;scanf("%d",a+n),a[n];n++)for(i=0;i<n-1;i++)
//n번째 수를 a배열에 입력받고 0이 아니면, n번째 버튼을 밟고있는 발의 반대발은 최대 n-1번째 버튼이므로 n-1까지 d배열 갱신
		if(d[i]){//d[i]==0 즉, 불가능한 상태이면 거르고,
			f=S(n-1,n); 
			f-1?//입력된 버튼이 바로 전에 입력된 버튼과 다르면
				d[n-1]=d[n-1]?//방금 입력된 버튼을 최근에 사용하지 않은 발로 밟는 경우 고려,
					m(d[i]+S(i,n),d[n-1])//d[n-1](이전턴(n-1)에 밟았던 발이 최근사용하지 않은 발이 됨으로)을
					:(d[i]+S(i,n))//최소값으로 최신화.
			:1;//이전 버튼과 같다면 이 과정에서 아무것도 하지 않으므로 해당 d[i]는 0으로 남아 계산에서 제외된다. 
			d[i]+=f;//역시 같다면 무조건 이전에 밟은 발로 방금 입력된 버튼도 밟는다. 달라도 이러한 경우는 가능하므로 고려해준다.
		}
	for(i=n-1;--i*(n-1);)d[i]?d[0]=m(d[0],d[i]):1;//입력이 끝나면 d[i]쭉 훑어 0이 아닌 값 중에서 비용의 최솟값 찾기
	printf("%d",n-1?d[0]:0);//이때 입력에서 0만 입력하여 바로 끝내는 경우에 대비하여 이럴때는 0을 출력하도록 한다.
}

djm03178 5년 전 1

요즘은 컴퓨터가 빨라져서 10억 정도까지는 됩니다. 하지만 100억은 여전히 너무 큽니다.

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

문제

문제

출처

ICPC

DDR 문제 O(n^2)풀이 시간초과 질문드립니다.

imno1234 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말