BOJ 7579번 앱

7579번: 앱

DP를 이용한 문제이다.

일반적으로 이러한 문제를 만나면, 확보되는 메모리를 인덱스로한다. 그렇게 해야 DP 테이블을 구한 뒤 문제에서 요구하는 인덱스의 값을 바로 출력 해 줄 수 있기 때문이다.

 

그런데 이 문제의 경우에는 확보할 메모리의 범위가 너무 넓다 (1 ~ 10,000,000) 비용의 범위가 (0 ~ 10,000) 인 것을 감안하면 결국 2byte 이상의 변수를 이용해야 하는데 그렇게되면 DP 테이블의 크기만 거의 20MB 가 되기 때문에 꺼려진다.

(msvc c++ 기준으로 기본 스택의 크기는 1MB밖에 안된다)

 

게다가 테이블을 만들기위해 저 테이블을 몇번이고 순회해야 하는데 시간또한 압박이 느껴진다.

 

그래서 고민끝에 비용을 인덱스로하고, 메모리를 값으로 하는 DP 테이블을 사용하기로 하였다.

 

비용의 범위는 0 ~ 10,000 인데 최대값 10,000은 문제의 조건에서 구할 수 있다.

(최대 앱 개수 * 앱당 최대 비용 = 100 * 100)

 

 

 

인덱스를 뒤집은 테이블을 만드는것은 기존에 포스팅한 수문 과 거의 동일하다.

 

DP테이블이 생성 된 이후에는 앞에서부터 (= 낮은 비용에서부터) 탐색하여 원하는 용량을 취할 수 있는 첫번째 인덱스를 출력해주면 끝난다.

 

 

 

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지