BOJ 문제풀이 4(W20)

dp로 상태를 정의하며 문제를 풀 때, 같은 패턴으로 항상 틀린다는 점을 발견했습니다.

서울에서 경산까지 문제의 경우(boj 14863)

1. me: k분 이하로 이동 가능하면 그때의 최대를 배열에 저장 아니라면 -INF를 리턴해주면 풀겠네!

dp배열을 서울부터 i까지 j를 이용하여 이동했을때 최대로 모금한 금액이라 정의한다면 아래와 같은 식을 쉽게 얻을 수 있구나!

$ \overset{\underset{\mathrm{}}{}}{dp\left ( i, j \right )=max\left ( dp\left ( i-1, j \right ), dp\left ( i-1, {j}' \right ) \right )}$

 

2. 손풀이 다 하고 컴퓨터로 옮기는중... 뭔가 갖고있는 정보가 부족한걸 알아챔(이 문제의 경우 이동에 걸린 총 시간이 필요함)

이를 테면 k분 이하로 현재 이동가능한지 불가능한지를 따져볼때 그 이전까지 이동에 소모된 시간이 필요함.

다시 1번으로...

 

저의 경우 정의한 점화식으로 문제가 정말 해결되는지 확인하는 과정이 항상 없는 것 같습니다.

앞으로 주의해야겠습니다.

 

아무튼 문제풀이 시작

 

14863 서울에서 경산까지

dp(i, j) := 서울에서 i까지 j분 이하로 이동 할 때 모금 한 최대 금액

위와 같이 디피 배열을 정의하면  $dp\left ( i, j \right ) = max\left ( dp\left ( i-1, j - WT_{i} \right ) + WM_{i}, dp\left ( i-1, j + RT_{i} \right ) + RM_{i} \right )$ 라는 점화식을 얻을 수 있습니다. (WT는 도보 시간 WM은 도보 금액)

이렇게 구한 점화식을 코드 레벨로 옮기면 문제는 풀 수 있습니다.

 

다만 약간의 친절을 더해 구현의 팁을 드리자면

1. 디피 배열에 접근 할 때 0보다 작은 값에 접근할 수 있다는 점

2. 배열을 전역으로 선언해야 하는점

이렇게 2가지 정도가 있습니다.🙂

 

16288 passport control

결국 주어진 수열 A에서 증가 부분 수열의 갯수가 K개 이하이면 YES를 출력하면 됩니다.

N이 최대 100이라 $O\left ( N^2 \right )$으로 해결 할 수 있습니다.

 

19582 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

디피로도 풀이 가능해 보이지만 저는 그리디로만 풀었습니다.

1번 대회부터 쭉 참가를 하다가 어느 순간 대회에 참여하지 못하게 되는 시점의 대회를 i라 할 때,

1부터 i-1 대회 중 상금이 가장 큰 대회j와 대회i를 교환 할 수 있고 대회i의 상금이 더 작으면 대회j를 빼고 대회i를 넣어주면 됩니다.

$O\left ( N \right )$안에 문제를 해결 할 수 있고 상금은 어차피 max값만 들고 있으면 됨으로 priority_queue를 이용하여 구현했습니다.

 

9655 돌게임

dp(i, j) := 돌이 i개 있고 j의 차례일때 j가 이기면 1 지면 0

위와 같이 정의하면 $dp\left ( i, j \right ) = {\left ( dp\left ( i-1, {j}' \right ) \wedge  dp\left ( i-3, {j}' \right ) \right )}'$를 얻을 수 있습니다.

돌게임2는 이번 풀이와 동일하고 돌게임 7도 있는데 기회가 되면 한번 풀어 보겠습니다.