Baekjoon 1535 안녕 JAVA

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

1535번: 안녕

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201535

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 사람들의 체력과 기쁨이 주어졌을 때, 세준이가 얻을 수 있는 최대 기쁨을 구하는 문제다

세준이의 체력은 100으로 제한을 둔다.

 

해당 문제는 전형적인 냅색 문제였고, dp를 이용해서 문제를 해결했다.

보통 2차원 배열을 이용해서 많이들 냅색을 해결하지만 1차원 배열을 이용하였고,

접근 방식을 앞이 아닌 뒤에서부터 체크하는 방향으로 하여 문제를 해결했다.

 

먼저 입력처리를 하고 dp는 세준이의 체력인 100 +1 한 크기로 지정한 뒤,

반복문을 돌리는데 먼저 사람의 수만큼 돌리고 그 안에서 세준이의 체력이 0이 될 때까지 --로 돌려준다.

 

이후 dp 값에 값을 저장하는데 여기서 비교를 해줘야 한다.

현재 저장된 값과, 새로운 사람의 기쁨 값 + 세준이의 체력 - 새로운 사람의 체력 한 값의 dp 값을 합한 것과 비교해

가장 큰 값을 저장하는 식으로 dp 배열을 갱신하고 최종적으로는 dp[100]을 출력해 준다.