[백준/JAVA]14501번 퇴사

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

14501번: 퇴사

 

 

퇴사[^1]

구현 과정

1. 첫 번째
   1. 첫날을 무조건 선택하여 해당 일의 T를 얻어 그다음 가능한 모든 경우의 수를 탐색
      1. 구현도 엉망으로 하였고 무엇보다 깔끔하게 받아들여지지 않았다.
2. 두 번째(외부 자료 참고 후)
   1. 첫 번째 했던 방식에서 연산을 무시할 경우와 연산에 대해 더 구체화하여 정의하였다
   2. 무시할 경우 : if ( i+t[i] ) > day
      1. 현재날과 해당 일의 소요일을 더하여 주어진 전체 요일과 크기를 비교한다
      2. 하나의 일이 제한된 기간에 수행이 가능함을 나타낸다
   3. 연산 : dp[i + t[i]] = max(dp[i + t[i]], dp[i + t[i]] + p[i])
      1. 이전에 수행했던 일과 현재의 일의 P를 더하여 x요일 일 때 최대의 수익을 저장한다.
      2. 위 max 부분은 3항 연산자로 처리
   4. 구현

public static void main(String[] args){  
    Scanner scanner = new Scanner(System.in);  

    int day = scanner.nextInt();  
    int[] durations = new int[day];  
    int[] incomes = new int[day];  
    int[] maxIncomeAtDay = new int[day + 1];  

    for (int i = 0; i < day; i++){  
        durations[i] = scanner.nextInt();  
        incomes[i] = scanner.nextInt();  
    }  

    for (int i = 0; i < day; i++) {  

        if (durations[i] + i > day) {  

        } 
        else {  
            maxIncomeAtDay[durations[i] + i] = maxIncomeAtDay[durations[i] + i] > incomes[i] + maxIncomeAtDay[i] ? maxIncomeAtDay[durations[i] + i] : incomes[i] + maxIncomeAtDay[i];
            // System.out.println(String.format("income : %d max : %d", incomes[i],maxIncomeAtDay[durations[i] + i]));
		}
	// else 연산에 처리되지 못한 경우 결과가 0이 된다. 그렇게 되면 순차적인 부분만 계산되고 연산의 예외가 발생하여 완전탐색에 실패한다
	// 다음 요일을 결정할 때 하나의 요일을 건너띄우는 경우도 파악하기 위해 처리 되지 않는 0를 이전 값으로 대체하는 코드
	maxIncomeAtDay[i+1] = maxIncomeAtDay[i+1] > maxIncomeAtDay[i] ? maxIncomeAtDay[i+1] : maxIncomeAtDay[i];
	}

// for (int i = 0; i < maxIncomeAtDay.length; i++){
	// System.out.println(String.format("day : %d Income : %d",i,maxIncomeAtDay[i]));
// 	}

    System.out.println(Arrays.stream(maxIncomeAtDay).max().getAsInt());  
}

회고

1. 모든 경우가 처리돼야 한다는 생각에 구현 방법이 잘 떠오르지 않았는데 각 요소에 집중하면 오히려 조건문이 쉽게 나오는 듯한 것을 느꼈다.
2. for문의 처리는 참고자료를 통해 배웠는데 사실 글을 정리하기까지 각주로 쓴 코드 부분이 왜 필요한지 이해 가 안된 부분이 있어 print로 찍어보았다. 그렇게 해보니 어느 정도 흐름을 파악하게 되어 이해할 수 있었다. 과연 이런 솔루션을 스스로 만들 수 있을지 아직 잘 모르겠다....

참고 자료

1. https://hidelookit.tistory.com/118