Educational Codeforces Round 133 (Div. 2) - 2-3 Moves 링크
(2022.08.29 기준 Difficulty *800)
(No cheating Yes study)

문제

2나 3만큼 왼쪽이나 오른쪽으로 갈 수 있을 때
0에서 시작하여 n까지의 최소 시간

알고리즘

'2나 3이라는 폭으로 n까지 도달하는 최소 시간' 말고는 아무 제약이 없으므로 이것만 생각해서 최적해를 찾는 그리디를 사용

풀이

2나 3은 한 번에 갈 수 있다.
4는 2 -> 4, 5는 2 -> 5, 6은 3 -> 6. 이들은 두 번만에 갈 수 있고
7~9는 4~6에서 3만큼 더해 세 번만에 갈 수 있다.
식으로 나타내면 ⌈n / 3⌉

주의사항

예외 케이스 1을 생각해야 한다.
1은 0 -> -2 -> 3. 두 번만에 갈 수 있다.

그리디는 목표만을 생각하며 최적해를 찾는 근사적인 방법이라 항상 예외 케이스가 있는지 생각해주자.

코드

import sys; input = sys.stdin.readline
from math import ceil

for _ in range(int(input())):
    n = int(input())
    print(ceil(n / 3) + (1 if n == 1 else 0)) # n이 1이면 답에 1을 더해준다.

여담

처음 코드포스 대회에 참가하여 처음 풀었던 문제
난이도가 코드포스에서 제일 쉬운 800이지만, 꽤 어려운 것 같다.
역시 글로벌