알고리즘 - 퇴사

문제

• 링크

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_14501_DP {
	
	private static int N, answer, size;
	private static int[] t,p, sum;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		size = N+5;
		t = new int[size]; 
		p = new int[size];
		sum = new int[size];
		
		for(int i = 0; i < N ; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			t[i] = Integer.parseInt(stk.nextToken()); 
			p[i] = Integer.parseInt(stk.nextToken());	
		}
		
		// N+1일 때 퇴사를 하면서 얻을 수 있는 최댓값을 구해야 하므로 N+1까지의 범위를 계산해준다
		for(int i = 0; i < N+1 ; i++) {
			sum[i] = Math.max(sum[i], answer);
			
			// t[i]번째 이후로 진행할 수 있기 때문에 현재 i에서 t[i]를 더해주어 
			// 저장된 값을 변경해주어야 한다.
			
			sum[t[i] + i] = Math.max(sum[t[i]+i], p[i]+sum[i]);
			answer = Math.max(answer, sum[i]);
		}
		//System.out.println(Arrays.toString(sum));
		System.out.println(answer);
		
		
		
		
	}
	
}

// DFS를 이용한 방식 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ_14501_DFS {
	
	private static int N, answer;
	private static int[] t,p;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		t = new int[N]; 
		p = new int[N];
		
		for(int i = 0; i < N ; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			t[i] = Integer.parseInt(stk.nextToken()); 
			p[i] = Integer.parseInt(stk.nextToken());
			
		}
		// n이 작기 때문에 => dfs로도 가능한 듯 
		// 시작점 => 0번째 인덱스 => value 0으로 설정 
		dfs(0,0);
		
	}

	private static void dfs(int index, int value) {
		// TODO Auto-generated method stub
		
		if(index >= N) {
			answer = Math.max(answer, value);
			return ;
		}
		
		if(index + t[index] <= N) {
			dfs(index + t[index], value + p[index]);
		}
		else {
			dfs(index + t[index], value);
		}
		
		dfs(index+1, value);
	}
	
	
}

회고

• dp라는 방식으로 풀 수 있다고 생각했지만, 오래 걸림

  • 링크

• DFS로도 풀 수 있다는 것을 블로그 보고 알게 됨

  • 오.... 링크

• 문제를 이해하는 데 너무 오래 걸리고, 더 준비를 해야 함

• 바로 코드를 작성하지 말자

• DFS, BFS 시간 복잡도 : 둘 다 O(N^2)(인접행렬), O(N+E)(인접리스트)

  • 링크