게임이론3 BOJ10714 케이크 자르기 2 10714번 케이크 자르기 2 자를 수 있는 케이크 조각의 크기가 주어질 때, JOI는 최선을 다해 케이크를 자르고, IOI는 양 끝 조각 중 무조건 큰 조각을 자른다. JOI가 얻을 수 있는 조각 합의 최댓값을 구해야 한다. 최선을 다하는 문제와 비슷하다. 다른 점은 JOI만 최선을 다한다 ⇒ dp배열에 두 명이 가진 케이크 양을 저장할 필요 없이 JOI가 얻게 된 조각 합의 양만 저장하면 된다. 케이크 조각은 직선형 배열이 아닌 원형 배열이다. 즉 시작과 끝이 정해져있지 않다 ⇒ i, j의 대소에 관계없이 전체 dp 배열을 채워야 한다. 가령 N=5일 때 dp[ 2 ][ 4 ]는 2, 3, 4번째 조각이 남아있을 때 dp[ 4 ][ 2 ]는 4, 5, 1, 2번째 조각이 남아있을 때 JOI가 얻은 케.. 2021. 1. 30. BOJ2618 경찰차 BOJ2618 경찰차 dp[ i ][ j ] dist = 마지막으로 A, B가 각각 i, j를 처리했을 때 움직인 총 거리 T = 가장 최근 사건을 처리하기 직전의 상태 STEP 1. w=1일 때 dp[ 1 ][ 0 ], dp[ 0 ][ 1 ] 갱신한다. STEP 2. w=2~W일 때 dp[ * ][ w ]와 dp[ w ][ * ]를 구한다. w-1번째, w번째 사건을 처리하는 경찰차가 각각 무엇인지에 따라 구해주면 된다. A-A: [ w-1 ][ * ] → [ w ][ * ] A-B: [ w-1 ][ * ] → [ w-1 ][ w ] B-A: [ * ][ w-1 ] → [ w ][ w-1 ] B-B: [ * ][ w-1 ] → [ * ][ w ] ㆍ*에 들어갈 수는 0부터 w-2까지여야 한다. ㆍdis.. 2021. 1. 29. BOJ11062 카드 게임 BOJ11062 카드게임 두 명 모두 최선의 전략으로 임할 때 얻는 점수를 구해야 한다. 게임이론 문제 분명 이전에도 본 적 있는 문제인데 헷갈려서 제꼈던 문제였을 것,, 최선의 전략으로 임한다는 말을 이해하기가 어려웠다. 이해하기보단 적용하기가? 미래 예측을 기똥차게 하겠단 소린데 어디까지 생각해야 할지, 완전 끝까지 생각하려면 어떻게 구현해야 할지가 막막했다. pair를 이용한 2차원 array로 풀었다. 재귀를 이용했으면 더 편했을 것도 같은데,, 구현할 때는 구할 수 있는 값부터 전체 배열을 채우는 식으로 빌드업함 dp[ i ][ j ] = 카드 j ~ i 로 게임을 진행할 때 { 먼저 시작한 사람의 점수, 상대방의 점수 } 카드 j ~ i 로 게임을 진행, X와 Y중 X가 먼저 카드를 뽑는다면 .. 2021. 1. 28. 이전 1 다음
