만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

교실 배정

시간 제한1초메모리 제한1024 MB

요약
교실 N개를 두 개씩 짝지어 반에 배정할 때, 지웅이가 받을 수 있는 초콜릿 파이의 최대 개수를 구합니다.
난이도

보통10점 중 6점

유형
동적 계획법, 비트 연산
정답자
아직 제출이 없습니다

문제

대구과학고는 현재 독서동을 수리하고 있어서 교실에서 대신 자습을 진행하기로 했다. 선생님들은 학생들이 떠들 것을 우려해 반별로 교실을 두 개씩 사용하기로 했다. 또한 교실마다 크기 차이가 있어 공평하게 사용하기 위해 매일 교실 배치를 바꾸어가며 자습을 진행하기로 하였다. 대구과학고에는 NN개의 교실과 ⌊N2⌋\lfloor \frac{N}{2} \rfloor개의 반이 있어, 각 반을 홀수 번호인 학생들과 짝수 번호인 학생들로 나누어 서로 다른 교실에서 자습하도록 할 생각이다.

입력

첫 번째 줄에 정수 NN이 주어진다.

출력

지웅이가 받을 수 있는 초코파이의 최대 개수를 출력한다.

제한

  • 2≤N≤302 \le N \le 30

힌트

  • 받을 수 있는 초코파이의 최대 개수는 2602^{60}을 넘지 않는다.
  • NN이 홀수인 경우에는 하나의 교실이 빈다.
  • ⌊x⌋\lfloor x \rfloor는 xx 이하의 최대 정수를 의미한다.

예제1

  1. 예제 1

    입력
    6
    
    예상 출력
    15