[JAVA] 백준 1970번 건배

카테고리 없음

by dajingjing 2022. 4. 7. 10:00

1970번: 건배

N명의 사람이 원판 테이블에 앉아서 콜라를 마시고 있다. 그 상황에서 두 사람이 짝을 지어서 건배를 하려 한다. 그런데 이들은 건배를 할 때, 보기 좋게 하기 위하여 마시고 있는 콜라의 브랜드

www.acmicpc.net

이 문제는 시작할때 가능한 경우의 수를 잘 생각해서 접근해야 한다.

오른쪽처럼 겹쳐서는 안되고 왼쪽처럼 안겹치기 위해서는 제일 처음 시작한 사람(기준점)이 어느 사람이랑 건배를 하냐에 따라서 답이 달라진다.

- 기준점 사람과 건배할 수 있는 사람이 있는 경우마다 이차원 배열 d[][]에 값을 저장해주고 최대 값을 구하는 것 (19~25번 줄)

- 기준점 사람이 건배할 사람이 없는 경우 (17번째 줄)

위 두가지 경우의 수를 생각해서 재귀함수를 만들면 된다.

DJ's Blog