SW Expert Academy 14692_통나무 자르기 문제풀이 in C++

2022년 10월 27일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

SWEA : 14692_통나무 자르기

문제 요구사항

---

• Alice와 Bob은 길이 N미터의 통나무를 자르는 게임을 한다.
• 게임은 Alice가 먼저 시작하며 그 이후 둘이 번갈아가면서 턴을 가진다.
• 각 턴을 맡은 사람은, 통나무를 두 조각으로 나누는데, 이 때 잘린 통나무가 모두 자연수(1 이상의 정수) 미터 길이를 가지도록 잘라야 한다.
• 더 이상 자를 수 없게 되는 사람이 진다. 누가 이기는가?

[입력]

• 첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.
• 첫 번째 줄에 정수 N이 주어진다. (2≤N≤ 109)

[출력]

• 각 테스트 케이스 마다 한 줄씩
• Alice가 이기면 “Alice”, 아니면 “Bob” 을 출력하라.

접근 방법

---

• 초기 접근 방법은 1이상만 자르면 되기 때문에 초기 받은 길이에서 -1씩 잘라가며 턴을 넘겼다. (당연히 시간초과)
• 위 접근 방법을 바탕으로 다시 보니, 초기 입력 받은 길이가 짝수면 해당 턴의 사람이 이기게 되고, 홀수면 해당 턴의 사람이 지게 된다.

풀이 순서

---

1. TC를 입력받아 해당 TC만큼 for문을 반복한다.
2. 초기 통나무 길이 distance를 입력 받는다.
3. 각 게임 첫번쨰는 Alice가 먼저 하므로, 짝수면 앨리스 승, 홀수면 밥이 이긴다.

소스코드

---

#include <iostream>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int TC;
	cin >> TC;

	for (int test_case = 1; test_case <= TC; test_case++) {
		long long distance;
		cin >> distance;

		// 굳이 반복 안 해도 짝수면 그 차례인 사람이 이김
		if (distance % 2 == 0) {
			cout << "#" << test_case << " " << "Alice" << "\n";
		}
		else {
			cout << "#" << test_case << " " << "Bob" << "\n";
		}

	}

	return 0;
}

문제 풀이 결과

---