문제 1024 세종이는 초콜릿을 좋아해
[만든사람 : ]
문제 설명
세종이와 예슬이가 초콜릿을 나누어 먹으려 한다.
초콜릿은 가로,세로 각각 x*y개의 조각으로 나누어져 있다.
예를 들어 x=3, y=5인 초콜릿은 다음 그림과 같은 모양이다.
초콜릿은 가로,세로 각각 x*y개의 조각으로 나누어져 있다.
예를 들어 x=3, y=5인 초콜릿은 다음 그림과 같은 모양이다.
둘은 초콜릿을 아주 좋아하기 때문에 자신이 더 많이 먹으려고 한다.
그래서 공평하게 게임을 통해 나누어 먹기로 했다. 게임 규칙은 다음과 같다.
- 자신의 차례가 되면 초콜릿을 두 부분으로 나눈다.
- 두 부분 중 크지 않은 부분을 내가 가져간다.
- 남은 부분으로 상대방이 다음 차례를 진행한다.
- 자기 차례에 초콜릿을 나눌 수 없으면 그 부분은 자기가 갖고 게임은 끝난다.
위의 경우 6가지 방법 중 하나로 나눌 수 있다.
세종이가 첫번째 차례이고, 초콜릿의 크기 x,y가 주어졌을 때 세종이가 받게 될 초콜릿 조각의 개수를 알아내는 프로그램을 작성해 보자. 단 세종이와 예슬이는 초콜릿을 최대한 많이 받기 위한 최선의 방법을 사용한다.
입력 설명
초콜릿의 크기 x와 y가 구분되어 입력된다. (1<=x,y<=10)
출력 설명
세종이가 받게 될 초콜릿 조각의 개수를 출력한다.
입력 예시 복사
2 3
출력 예시 복사
4
도움
초콜릿 조각을 많이 받으려면 가져갈 수 있을 때 최대한 많이 가져오는 전략이 필요하다.
출처/분류