BOJ 7579 - 앱 (https://icpc.me/7579)
쉬운 문제라고 생각해서 도전했다가 5시간 걸렸다.
몇 개월 전이었다면 스스로 푸는 것을 포기하고 다른 사람 풀이를 찾아봤을텐데, 결국 성공했기 때문에 너무 기쁘다.
풀고나서 다른 분들 코드를 확인해보니, 좀 더 효율적인 방법도 있었고.. 일단 내 방법도 써보려고 한다.
접근 방법
app[n][0]: n번째 앱의 메모리app[n][1]: n번째 앱의 활성화 비용
1) DP 배열을 D[2][10001]로 만든다.
예제 입력 크기에 알맞게 만들어줄 수도 있지만, N 제한 및 Cn 제한이 100이기 때문에 편의상 10001로 만들었다.
D[0][n]: 앱 활성화 비용으로 n만큼 사용했고 i번째 앱을 비활성화 하지 않았을 때 확보되는 메모리의 최대값D[1][n]: 앱 활성화 비용으로 n만큼 사용했고 i번째 앱을 비활성화했을 때 확보되는 메모리의 값
2) 2중 for문으로 배열을 채워준다.
처음에 여기서 매우 고생했다. 각각의 값을 한번씩만 사용해줘야 하는 상황이라 별도로 처리해줘야 하는 부분이 있었는데 경험 부족으로 애를 먹고 있었고, DP 배열을 [2][10001]로 설계해서 그 문제를 해결했다.
-> 어디까지나 내가 푼 방법이 이렇고, 실제로는 감소하는 반복문을 돌려주면 이런 문제 없이 해결할 수 있다. 나는 증가하는 반복문을 돌려줬기 때문에, 각 배열에 들어있는 값에 app[n][0]을 중복으로 더해주는 참사가 있었다.
2-1) D[0][n] 값을 기반으로 D[1][n]을 채워주기
점화식 : D[1][j] = D[0][j - app[i][1]] + app[i][0]
2-2) D[0][n]을 갱신해주고 D[1][n] 초기화
D[0][n]에 D[1][n]보다 큰 값이 있는 경우 갱신하지 않고, 그렇지 않으면 갱신해줬다.
그런뒤에 D[1][n]값을 초기화해서 다음 반복문 돌릴 때 차질이 없도록 처리했다.
3) DP 배열을 0부터 검사해서 확보해야하는 메모리값보다 크거나 같으면 ans에 저장
추후에 이 문제를 다시 풀어보고 글을 갱신해야겠다.