글 읽기 - 시간초과... 도와주시면 감사합니다..(1로 만들기)

h00201 6년 전 0

정답은 맞는데 너무 돌아가는건지 아니면 어디서 무한루프가 생기는 건지.. 시간초과만 뜨네요.

좀 더 효율적으로 만들 수 있는 방법이 있을까요?

#include<iostream>
#include<stdio.h>
 
using namespace std;
 
int main() {
    int a[1000001];
    int input;
    int count = -1;

    scanf("%d", &input);
 
    for(int i = 0; i < input; i++) { 
        if(i == 0) a[i] = 0; // 숫자 1일 때
        else if(i == 1) a[i] = 1; // 숫자 2일 때
        else {
        	for(int j = i; j >= i / 3; --j) {
        		if(j * 3 == i + 1 || j * 2 == i + 1 || j == i) count = a[j - 1]; // *3, *2, +1에 해당하는경우 저장
				if(count != -1 && count < a[i]) a[i] = count + 1; // 수를 비교해보고 더 적은 값을 반영.
				count = -1;
        	}
        }
        if(i != 1000001) a[i+1] = a[i] + 1; // 다음 값 초기화
    }    
 
    printf("%d", a[input-1]);
    return 0;
}

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

문제

문제

출처

ICPC

시간초과... 도와주시면 감사합니다..(1로 만들기)

h00201 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말