[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 14501 : 퇴사

 

www.acmicpc.net/problem/14501

14501번: 퇴사

 

문제 풀이

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

public class Main {

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st = new StringTokenizer( br.readLine() );
		int n = Integer.parseInt( st.nextToken() ), i, j;
		int a[][] = new int[n][2];
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < 2; j++ ) 
				a[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
		
		int dp[] = new int[n];
		int s, m;  // sum, max
		for( i = 0; i < n; i++ ) {
			m = 0;
			for( j = 0; j < i; j++ ) {
				s = j + a[j][0];
				if( s <= i ) {
					if( m < dp[j] )
						m = dp[j];
				}
			}
			dp[i] = m + ( n-i >= a[i][0] ? a[i][1] : 0 );
		}
		
		int res = 0;
		for( int r : dp )
			if( res < r )
				res = r;
		System.out.println( res );
	}
}

 

i	0	1	2	3	4	5	6
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	10	20	10	30	45	30	45

 

*  dp[i] => i 일째에 잡힌 상담을 할 시, 받을 수 있는 최대 금액 ( i 는 편의상 0부터 시작 )

*  만약 i 일째에 잡힌 상담을 할 시, 다음 상담은 i+Ti 일째 부터 할 수 있다
( ex) 0일째에 3일 짜리 상담을 하면, 다음 상담은 3일째 부터 할 수 있다 )

*  따라서 i 일째에 상담을 하려 할 때, 그 전 가장 최근에 한 상담은 j ( 0 <= j < i ) 일째 까지 탐색하면서 j+Tj가 i보다 작거나 같을 경우 중에 있다.
( ex) 3일째에 상담을 하려 할 때, 그 전 가장 최근에 한 상담은 0일째 ( 0+3 ) 또는 2일째 ( 2+1 ) 이다 )

*  이 중 금액이 가장 큰 날을 골라 i일에 상담하면 받을 수 있는 금액과 더한다.
( ex) 0일째의 10과 2일째의 10이 같다. m 은 10 이고, 3일째의 상담을 하면 dp[3] 은 10+20 과 같다 )