[코드포스 - 1716A] 2-3 Moves

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int t, n; cin >> t;

	for (int i = 0; i < t; ++i)
	{
		cin >> n;
		if (n == 1) cout << 2 << "\n";
		else
		{
			int add = n % 3 == 0 ? 0 : 1;
			cout << n / 3 + add << "\n";
		}
	}

	return 0;
}

---

||사고 과정

일단 최소 이동 횟수가 나오려면 최대한 3으로 많이 가야하니까 목적지에서 3을 나누어야겠다고 생각했다.

3으로 나눈 나머지는 0, 1, 2 세가지 경우의 수가 나오는데 이 각 수에 2를 어떻게 넣느냐를 생각했다.

 

1이 남은 7같은 경우에는 3으로 2번 이동해서 6만큼 가고 여기서 3만큼 한번 뒤로가고 2만큼 두번 가면 7이 된다.

하지만 애시당초 3만큼 1번가고 2만큼 2번가면 최소 3번만에 갈 수가 있다.

즉, n / 3 + 1을 하면 최소 횟수가 나왔다.

이는 1이 남는 모든수에 해당하고 2도 비슷한 방식으로 +1을 해주면 최소 횟수가 나왔다.

 

그렇기에 나머지 값이 1,2가 나오면 단순 +1 을 해주면 되고 0이면 나눈 값을 반환하면 되겠다.

 

예외로 1은 무조건 0부터 시작하기에 2만큼 뒤로 갔다 3만큼 앞으로 가야하기에 1은 예외처리 했다.

---

||사용 기법

• Greedy