[백준] [의문]14501번- 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

 

문제 이해

: 백준이는 오늘로부터 N+1일에 퇴사할 예정. 남은 N일간 최대한 많이 상담을 할거다

=> N일동안 최대한 벌고 나가겠다.

 

입력

- N(일 할 수 있는 일수) (1~15)

- Ti(상담 기간) (1~5)

- Pi(상담에 따른 금액) (1~1000)

 

 

시간제한이나 입력값 크기를 보면 뭘 하든 시간 제한이나 메모리 제한에 걸리진 않을 것 같다.

부분 집합으로 완전탐색을 돌릴 수도 있다.

백준의 분류로는 다이나믹으로 되어있긴한데 이번주는 순열, 조합, 부분집합 돌리는 날이라 그냥 부분집합을 썼다.

결과

 

 

출력

백준이가 얻을  수 있는 최대 이득

 

 

걸린 시간

- 입력처리 코드 ; 4분 44초

- 1차 코드 : 20분

- 예외케이스 문제: 질문란의 예외케이스를 다 돌려봐도 문제가 없었다, 그리고 예외 문제가 아니었음.

 

 

public class Main {
	static int N, maxPay = 0, tmp;
	static int[] T, P;
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token;
		
		N = Integer.parseInt(in.readLine());
		
		T = new int[N];
		P = new int[N];
		
        // 입력
		for (int i = 0; i < N; i++) {
			token = new StringTokenizer(in.readLine());
			tmp = Integer.parseInt(token.nextToken());
			if(tmp>(N-i)) continue;		// 만약 남은 일자보다 상담일이 길면 아에 안받겠다.
			T[i] = tmp;
			P[i] = Integer.parseInt(token.nextToken());
		}
		
		subset(0,0,0,0);
		
		System.out.println(maxPay);

	}
	private static void subset(int start, int now, int pay, int day) {
		// 기저조건
		if(now > N || day>N) {
			return;
		}

		maxPay = Math.max(maxPay, pay);
		
		for (int i = start; i < N; i++) {
			StringBuilder builder = new StringBuilder();
			
			tmp = T[i];	
			
            // 상담일수가 0인건 입력 안받은 날이니까 뭐 더하지 말고 넘겨야
			if(tmp==0) subset(i+1, now, pay, day);
			else subset(i+tmp, now+tmp, pay+P[i], day+tmp);
		}
	}

 

의문

subset(0,0,0,0) 호출을 원래는 아래처럼 짰는데 이게 문제였다.

80퍼에서 틀렸습니다가 뜨는데 저 조건을 없애버리고 호출만 하니까 통과가 되더라.

내가 따로 테케를 만들어서 돌려봐도 잘만 작동되는데 뭐가 문제인지 모르겠다.

IntStream에 문제가 있나 싶어 따로 합을 구해봐도 문제는 같더라.

 

if(IntStream.of(T).sum() == N) maxPay = IntStream.of(P).sum();	//  모든 일자가 1일때 걸림
else subset(0,0,0,0);