글 읽기 - 실행 시간 차이 질문드립니다.

jh1one 5년 전 1

bottom-up 방식으로 해당 문제를 해결하였고 실행 시간은 4ms가 나왔습니다.

0ms가 걸린 답안들을 보며 다른 방식의 문제 해결 방법도 공부하던 중 같은 bottom-up 방식인데 시간이 0ms가 걸린 답안을 발견하였습니다.

이상하다 싶어 그대로 복붙해서 돌려봐도 여전히 4ms가 나왔습니다.

이 점이 궁금한 이유는 문제를 풀고 나서 제 결과보다 더 효율적인 답안들을 찾아 볼 때 실행 시간이나 사용 메모리를 기준으로 찾아보기 때문입니다. (오답풀이 한다는 차원에서 이 방법을 취하고 있습니다.)

이러이러한 방법으로 더 효율적으로 풀 수 있구나 하고 깨우침을 얻어가는데 같은 코드에서 결과가 다르게 나오니 실행 결과를 어디까지 믿어야 하는지 의문이 듭니다.

이상 아직까지 시간복잡도 계산이 어려워 혼자서는 정확한 판단이 조금 힘든 초보자의 질문이었습니다.

아래는 혹시 몰라 위에서 언급한 코드추가입니다.

#include <cstdio>

int main() {
	int n, c[1000001] = {0, };
	scanf("%d", &n);
	for (int i = 2; i <= n; i++) {
		int min = c[i - 1];
		if (i % 3 == 0 && min > c[i/3])
			min = c[i / 3];
		if (i % 2 == 0 && min > c[i/2])
			min = c[i / 2];
		
		c[i] = min+1;
	}
	printf("%d\n", c[n]);
	return 0;
}

djm03178 5년 전 3

실행 시간 계산 자체가 4ms 단위로밖에 안 됩니다. 0ms로 나온 코드나 4ms로 나온 코드나 실제로는 0.00000001초의 차이일 수도 있습니다. 게다가 채점 당시의 서버 상태에 따라서도 그 속도는 얼마든지 뒤집어질 수 있습니다. 그 정도 차이에 너무 연연하실 필요는 없어 보입니다.

ccc12345 1년 전 0

저도 1로만들기 어떻게 0ms으로만들지 고민하다가 57회이상 반복되면 나눈수중 가장큰값으로 점프하는 방식이 있어요 그런데도 여전히 4ms에요

// Online C compiler to run C program online
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    vector <int> writedown;
    int N;
    int arr[1000001];
    scanf("%d", &N);
    vector <int>::iterator it;
    arr[N] = 0;
    int jump = 0;
    for (int i = N; i > 0; i--) {
        it = find(writedown.begin(), writedown.end(), i);
        if ((it != writedown.end())) {
            remove(writedown.begin(), writedown.end(), i);
        }
        if (jump > 57) {//57회를 넘을시 때려친다
            i = *max_element(writedown.begin(), writedown.end());
            remove(writedown.begin(), writedown.end(), i);
            jump = 0;
        }
        if (i % 2 == 0) {
            it = find(writedown.begin(), writedown.end(), i / 2);
            if ((it != writedown.end())) {
                if (arr[i] + 1 < arr[i / 2]) {//비교
                    arr[i / 2] = arr[i] + 1;//덮어쓰기기
                }
                //아니면놓아두기(else생략)
            }
            else {
                writedown.push_back(i / 2);//writedown에 비교할 필요가 있음을 알림
                arr[i / 2] = arr[i] + 1;
            }
        }
        if (i % 3 == 0) {
            it = find(writedown.begin(), writedown.end(), i / 3);
            if ((it != writedown.end())) {
                if (arr[i] + 1 < arr[i / 3]) {//비교
                    arr[i / 3] = arr[i] + 1;//덮어쓰기기
                }
                //아니면놓아두기(else생략)
            }
            else {
                writedown.push_back(i / 3);//writedown에 비교할 필요가 있음을 알림
                arr[i / 3] = arr[i] + 1;
            }
        }
        it = find(writedown.begin(), writedown.end(), i - 1);
        if ((it != writedown.end())) {
            if (arr[i] + 1 < arr[i - 1]) {//비교
                arr[i - 1] = arr[i] + 1;//덮어쓰기기
            }
            //아니면놓아두기(else생략)
        }
        else {
            arr[i-1] = arr[i] + 1;
        }
        jump = jump + 1;
    }
    printf("%d", arr[1]);
    return 0;
}

ccc12345 1년 전 1

규칙을 찾았는데 재귀함수 형태로 풀면 0ms가 나오는것 같아요

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

문제

문제

출처

ICPC

실행 시간 차이 질문드립니다.

jh1one 5년 전 1

djm03178 5년 전 3

ccc12345 1년 전 0

ccc12345 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말