3. PS장학금(하)
View as PDF컴공이는 평행세계에 존재하는 다른 조선대학교에 다니고 있다.
그곳의 IT융합대학은 \(N\)년제이며, 알고리즘 공부를 장려하기 위한 PS장학금이 있다.
PS장학금의 금액은 매 학기 달라질 수 있고 신청에는 몇 가지 제한이 있다.
PS장학금은 같은 해의 1학기와 2학기 중 한 번만 신청할 수 있으며, 두 학기 모두 신청하지 않을 수도 있다.
또한 연속된 해의 동일한 학기에는 신청할 수 없다.
예를 들어, 2학년 1학기에 장학금을 받았다면, 2학년 2학기와 3학년 1학기에는 받을 수 없다.
컴공이는 알고리즘 성적이 우수하기 때문에 신청만 하면 지급받을 수 있다.
\(N\)년간의 장학금 액수가 주어졌을 때 컴공이가 받을 수 있는 최대 장학금은 얼마일까?
입력
- 첫 번째 줄에 \(N\)이 주어진다.\((1≤N≤10,000)\)
- 그 다음 줄부터 \(N\)개의 줄에 \(N\)년간의 1학기 장학금 액수와 2학기 장학금 액수가 한 칸으로 구분되어 주어진다.
- 장학금 액수는 1,000 이하의 자연수이다.
출력
컴공이가 받을 수 있는 최대 장학금을 출력한다.
입력 예시 1
3
3 1
1 2
1 4
출력 예시 1
7
Comments
전형적인 조약돌 놓기 문제입니다. 수업시간에 배웠던 내용을 어떻게 매칭할 수 있을 지 생각해 보세요, 여기서는 패턴이 3개 입니다. 패턴0은 장학금 안받기, 패턴1은 1학기만 장학금, 패턴 2는 2학기만 장학금... 이렇게 생각하면, 각 패턴들 마다 서로 인접할 수 있는 패턴이 정의되지요?