글 읽기 - 두 접근 방법 간 시간복잡도 차이를 잘 모르겠습니다.

jaejin0209 5년 전 0

처음 문제를 보고 단순한 메모이제이션 문제라 생각해 표현해야 하는 값 price 와 사용할 수 있는 가장 높은 가치의 동전의 index인 maxIndex를 재귀함수의 입력으로 받아 가장 낮은 가치의 동전부터 가능한 한 높은 가치의 동전을 사용한 후 재귀하는 형태로 설계했습니다. 이것이 1번 접근방식 코드입니다.

그러나 문제에서 시간초과가 나와 막막해하던 중 학창시절 비슷한 문제를 풀 때 편의를 위해 가장 큰 가치의 동전의 갯수로 가능한 경우를 나열하고 나머지를 채워나가는 식으로 접근했던 것이 떠올라 그 방식으로 구현했습니다. 이것이 2번 접근방식 코드입니다.

겉보기에는 시간복잡도에서 차이가 있지 않을것이라 생각했는데 2번 접근방식의 경우 시간초과 없이 정답처리 됐습니다. 두 접근방식 간 시간복잡도는 어떻게 차이가 나는걸까요?

//1번 접근방식
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class N2293 {
	static int n,k;
	static ArrayList<Integer> value;
	static int[][] number;
	public static void main(String[] args) throws IOException{
		input();
		System.out.println(getNumber(k,n-1));
	}
	static void input() throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		number = new int[k+1][n];
		for(int i=0;i<=k;i++) {
			for(int j=0;j<n;j++) {
				number[i][j] = -1;
			}
		}
		value = new ArrayList<Integer>();
		for(int i=0;i<n;i++) {
			value.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(value);
	}
	
	static int getNumber(int price, int maxIndex) {
		if(number[price][maxIndex]>-1) {
			return number[price][maxIndex];
		}
		if(price == 0) {
			return number[price][maxIndex] = 1;
		}
		if(maxIndex==0) {
			if(price%value.get(0)==0) {
				number[price][0] = 1;
			}
			else {
				number[price][0] = 0;
			}
			return number[price][0];
		}
		int sum = 0;
		for(int i=0;i<=maxIndex;i++) {
			if(price<value.get(i)) {
				break;
			}
			sum+=getNumber(price-value.get(i),i);
		}
		number[price][maxIndex] = sum;
		return number[price][maxIndex];
	}
}

//2번 접근방식
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class N2293{
	static int n,k;
	static ArrayList<Integer> value;
	static int[][] number;
	public static void main(String[] args) throws IOException{
		input();
		System.out.println(getNumber(k,value.size()-1));
	}
	static void input() throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		number = new int[k+1][n];
		value = new ArrayList<Integer>();
		for(int i=0;i<n;i++) {
			value.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(value);
	}
	static int getNumber(int k, int maxIndex) {
		if(number[k][maxIndex]!=0) {
			if(number[k][maxIndex]==-1) {
				return 0;
			}
			return number[k][maxIndex];
		}
		if(maxIndex==0) {
			if(k%value.get(maxIndex)==0) {
				number[k][maxIndex] = 1;
				return 1;
			}
			else {
				number[k][maxIndex] = -1;
				return 0;
			}
		}
		int sum = 0;
		for(int i=0;i<=(int)k/value.get(maxIndex);i++) {
			sum+=getNumber(k-(value.get(maxIndex)*i),maxIndex-1);
		}
		if(sum == 0) {
			number[k][maxIndex] = -1;
			return 0;
		}
		return number[k][maxIndex] = sum; 
	}
}

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

문제

문제

출처

ICPC

두 접근 방법 간 시간복잡도 차이를 잘 모르겠습니다.

jaejin0209 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말