백준 11062번 카드게임
< 11062번 카드게임 - 마포 코딩박 >
사용한 알고리즘: DP
일렬로 놓여있는 카드를 근우부터 시작하여 근우와 명우 두사람이 번갈아가며 뽑을 때, 근우가 얻을 수 있는 최대 점수를 구하는 문제였습니다.
문제풀이는 다음과 같습니다.
(1) (코드 6~9)
'dp[a][b][1] : 카드 왼쪽 index: a, 오른쪽 indx b, 근우차례 일 때, 근우가 얻을 수 있는 최대 점수'
'dp[a][b][0] : 카드 왼쪽 index: a, 오른쪽 indx b, 명우차례 일 때, 근우가 얻을 수 있는 최대 점수' 라고 설정하였습니다.
(2) (코드 11~28)
dp 값을 구하는 함수를 만들었습니다. dp값은 근우가 얻을 수 있는 최대 점수임을 생각합니다.
왼쪽 index: start, 오른쪽 index: last 상태로 남은 카드 상태에서,
근우 차례일 때는 왼쪽, 오른쪽 중 하나를 근우가 얻고, 게임을 진행 했을 때 둘 중 '최대' 값이 dp값이고,
명우 차례일 때는 왼쪽, 오른쪽 중 하나를 없애고, 게임을 진행 했을 때 둘 중 '최소'값이 dp값입니다.
카드가 한장 남았을 때 (start==end) 가 기저값입니다.
사용한 알고리즘: DP
일렬로 놓여있는 카드를 근우부터 시작하여 근우와 명우 두사람이 번갈아가며 뽑을 때, 근우가 얻을 수 있는 최대 점수를 구하는 문제였습니다.
문제풀이는 다음과 같습니다.
(1) (코드 6~9)
'dp[a][b][1] : 카드 왼쪽 index: a, 오른쪽 indx b, 근우차례 일 때, 근우가 얻을 수 있는 최대 점수'
'dp[a][b][0] : 카드 왼쪽 index: a, 오른쪽 indx b, 명우차례 일 때, 근우가 얻을 수 있는 최대 점수' 라고 설정하였습니다.
(2) (코드 11~28)
dp 값을 구하는 함수를 만들었습니다. dp값은 근우가 얻을 수 있는 최대 점수임을 생각합니다.
왼쪽 index: start, 오른쪽 index: last 상태로 남은 카드 상태에서,
근우 차례일 때는 왼쪽, 오른쪽 중 하나를 근우가 얻고, 게임을 진행 했을 때 둘 중 '최대' 값이 dp값이고,
명우 차례일 때는 왼쪽, 오른쪽 중 하나를 없애고, 게임을 진행 했을 때 둘 중 '최소'값이 dp값입니다.
카드가 한장 남았을 때 (start==end) 가 기저값입니다.
질문 드려도 될까요??
답글삭제choic 함수에서 ret값을 참조형으로 보내지 않으면 시간초과가 나는데 혹시 이유를 알려주실수 있나요..?ㅠ
&을 ret 앞에 붙이는 것을 말씀하시는 것 같습니다.
삭제&을 붙이는 이유는 ret 과 dp 가 일심 동체가 된다고 생각해 주시면 될 것 같아요. 즉 ' &ret = dp ' 라고 한 뒤, ret 값을 변경하면 dp 값이 자동으로 변경 됩니다.
반대로 ret = dp 라고 하면, ret은 단순히 dp 값만 받아 오는 것입니다.
이후 ret을 변경해도 dp 값은 변경 되지 않습니다. 따라서 매 탐색 결과가 dp에 업데이트 되지 않아 시간초과가 나는 것 같습니다!