[백준/C++] 1107번. 리모컨

문제

1107번: 리모컨

---

1. 첫 번째 풀이

사고 과정

이 문제는 옮길 수 있는 채널을 하나 구해서 채널을 옮기고, 거기서 +, -를 조작해 원하는 채널을 만드는 문제다.

 

예를 들어 5457번 채널을 맞추는데 6, 7, 8번이 고장났다면 5455번으로 이동한 후 +를 2번 누르면, 6번 버튼을 눌러 이동할 수 있다.

 

버튼을 누르는 최소 횟수를 구해야 했기에, 반대로 답에서부터 거슬러 올라가기로 했다.

 

위와 같은 예시를 살펴보자. 먼저 5457로 옮길 수 있는지 검사한다. 불가능하다.

 

그럼 +, -를 한 번씩 눌러 5456, 5458 두 가지 경우의 수를 살펴본다. 아직 둘 다 만들 수 없으니, 다음으로 넘어간다.

 

2번씩 누르면 5455, 5459가 나오는데, 둘 다 가능하다. 여기선 작은 수가 자릿수도 적을 확률이 높으므로, 5455를 택해보자.

 

5455, 4번의 버튼을 눌러야 한다. 이는 5455의 자릿수와 일치한다.

우린 5457에서 5455로 가는데 2번의 버튼을 눌렀다. 따라서 4 + 2 = 6을 반환한다.

 

이처럼 주어진 목표 n을 기준으로, +와 - 두 방향으로 물결치듯 이동한다. 만약 벡터에 +나 - 버튼을 누른 횟수를 저장해둔다면, 2, 1, 0, 1, 2 같은 모양새가 될 것이다. (n번째 값이 0이다.)

 

1. n부터 시작, 좌우로 +, -를 한 번씩 눌러가며 이동한다.
2. 만약 채널을 만들 수 있다면 그 채널을 택한다. 따라서 해당 채널의 자릿수를 센다. (5455면 4)
3. 해당 채널에서 n까지 가는데 필요한 +, - 버튼 수를 자릿수에 더하고, 출력한다.

말로 풀어쓰려니 쉽지 않다. 예시와 함께 보면 이해하기 조금 수월할 것이다.

 

코드

#include <iostream>
#include <vector>

std::vector<int> wrongNums;

// 자릿수를 반환
int getIntPlace(int n) {
	if (n == 0) {
		return 1;
	}

	int count = 0;

	while (n > 0) {
		count++;
		n /= 10;
	}

	return count;
}

// 해당 채널을 바로 만들 수 있는 지 검사한다.
bool canMakeChannel(int channel) {
	int r;

	while (channel > 0) {
		// 각 자릿수를 검사
		r = channel % 10;

		// wrongNums에 있는 값이면 false 리턴
		for (auto& num : wrongNums) {
			if (r == num) {
				return false;
			}
		}
		// 검사한 자리 제거
		channel /= 10;
	}

	return true;
}

int main() {
	// 입력
	int n, m;
	std::cin >> n >> m;

	wrongNums.resize(m);
	for (auto& num : wrongNums) {
		std::cin >> num;
	}

	// 계산
	// 모든 숫자 버튼이 고장난 경우 +, -만 조작
	// 98 ~ 103번 채널은 +, -만 하는 게 더 이득
	if (m == 10 || (98 <= n && n <= 103)) {
		std::cout << ((n >= 100) ? n - 100 : 100 - n);
		return 0;
	}

	for (int i = 0; i <= 50000000; i++) {
		// + 버튼 조작
		if (n - i >= 0 && canMakeChannel(n - i)) {
			std::cout << getIntPlace(n - i) + i;
			return 0;
		}

		// - 버튼 조작
		if (canMakeChannel(n + i)) {
			std::cout << getIntPlace(n + i) + i;
			return 0;
		}
	}
}

 

결과

하지만 결과는 틀렸습니다.

---

2. 마지막 풀이

사고 과정

반례를 찾아 게시판을 헤메다, 겨우 발견한 단비같은 반례.

 

123

3

1 2 5

output: 26

answer: 23

 

채널을 지정할 수 있더라도, +, -만 쓰는 게 더 이득인 경우다.

 

실제론 100에서 23번 +를 누르면 되지만, 내 로직에선 99를 누르고(2) +를 24번 누르기에 26이 나왔다.

 

따라서 for문에서 구한 답을 answer에 저장해두고, abs(n - 100)과 비교해 작은 걸 출력하게 만들었다.

 

이외에도 몇 가지 문제가 더 있었다.

우선, canMakeChannel 함수가, 0번 채널인 경우 검사없이 true를 리턴했다. 그래서 0에 대한 예외를 추가했다.

 

앞서 삼항 연산자를 사용했던 부분은, <cstdlib>의 abs 함수를 사용하기로 바꿨다.

 

그리고 for문의 조건문을 없애, 무한 반복하게 만들었다. 채널의 수가 무한이기도 하고, 무한루프에 빠지는 경우는 모든 수를 쓸 수 없는 경우 뿐인데, 이는 앞서 처리했기 때문이다.

 

코드

#include <iostream>
#include <cstdlib>
#include <vector>

std::vector<int> wrongNums;

// 자릿수를 반환
int countDigits(int n) {
	if (n == 0) {
		return 1;
	}

	int count = 0;

	while (n > 0) {
		count++;
		n /= 10;
	}

	return count;
}

// 해당 채널을 바로 만들 수 있는 지 검사한다.
bool canMakeChannel(int channel) {
	// 0번 채널을 만들 경우
	if (channel == 0) {
		// wrongNums에 0이 있다면 false
		for (auto& num : wrongNums) {
			if (num == 0) {
				return false;
			}
		}

		// 없다면 true
		return true;
	}

	int r;

	while (channel > 0) {
		// 각 자릿수를 검사
		r = channel % 10;

		// wrongNums에 있는 값이면 false 리턴
		for (auto& num : wrongNums) {
			if (r == num) {
				return false;
			}
		}
		// 검사한 자리 제거
		channel /= 10;
	}

	return true;
}

int main() {
	// 입력
	int n, m;
	std::cin >> n >> m;

	wrongNums.resize(m);
	for (auto& num : wrongNums) {
		std::cin >> num;
	}

	// 계산
	// 모든 숫자 버튼이 고장난 경우 +, -만 조작
	// 98 ~ 103번 채널은 +, -만 하는 게 더 이득
	if (m == 10 || (98 <= n && n <= 103)) {
		std::cout << abs(n - 100);
		return 0;
	}

	int answer;
	for (int i = 0; ; i++) {
		// + 버튼 조작
		if (n - i >= 0 && canMakeChannel(n - i)) {
			answer = countDigits(n - i) + i;
			break;
		}

		// - 버튼 조작
		if (canMakeChannel(n + i)) {
			answer = countDigits(n + i) + i;
			break;
		}
	}

	// +, -로 조작한 횟수보다 i가 커지면, +, -로 조작
	if (answer > abs(n - 100)) {
		answer = abs(n - 100);
	}

	std::cout << answer;
}

chatGPT의 도움을 받아, getIntPlace의 이름을 countDigits로 바꿨다. 역시 GPT가 이름 하난 잘 짓는다.

 

결과

 

드디어 성공했다.

---

개선

사고 과정

가장 먼저 떠올린 건, canMakeChannel 함수와 countDigits 함수의 통합이었다. 굳이 반복문을 두 번 돌릴 필요 없이, canMakeChannel 함수가 자릿수를 반환, 불가능 시 -1을 반환하면 될 거라 생각했기 때문이다.

 

하지만 countDigits는 canMakeChannel이 성공했을 때, 딱 1번만 실행되기 때문에, 전체적으로 큰 영향을 미치진 않는다. 최악의 경우 6번 더 연산하는 게 전부니, 굳이 합치면 코드 알아보기만 더 어려워질 것이다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/12983263

ruz님의 코드. 숏코딩이 아니면서 알아보기도 쉬워 바로 가져왔다.

 

내 코드와 비교

이 분은 유효한 값 검사에 bool 배열을 사용했다. 나는 canMakeChannel 함수 내에서, 각 자리가 wrongNums에 있는지 순차적으로 비교했기에, wrongNums의 크기만큼 비교를 반복했다. 하지만 이 분처럼 bool을 쓰면, 1번 만에 알 수 있다.

 

나는 반복을 통해, 가까운 채널들이 유효한지 검사했다. 그에 반해 이 분은, 6자리가 될 때까지 유효한 숫자들로 채널을 우선 만든 뒤, 기존에 구해뒀던 minWay(abs(100 - n), 0으로 만들고 +해보기)보다 작은 경우 갱신해나가는 식으로 반복했다.

 

나의 반복 횟수는 +, -를 누르는 횟수에 비례하며, 최악의 경우에도 약 50만 번 아래로 반복된다.

이 분의 경우는 유효한 숫자에 비례하며, 만약 9개 숫자를 쓴다면 9^6 = 531,441 번 반복될 수 있다. 미세한 차이로 내 코드가 나은 것 같다.

 

그래서 bool 배열을 써서, 다시 한 번 문제를 풀어봤다.

 

코드

#include <iostream>
#include <cstdlib>
#include <vector>

std::vector<bool> isBroken(10, false);

// 자릿수를 반환
int countDigits(int n) {
	if (n == 0) {
		return 1;
	}

	int count = 0;

	while (n > 0) {
		count++;
		n /= 10;
	}

	return count;
}

// 해당 채널을 바로 만들 수 있는 지 검사한다.
bool canMakeChannel(int channel) {
	// 0번 채널을 만들 경우
	if (channel == 0) {
		if (isBroken[0]) {
			return false;
		}

		return true;
	}

	int r;

	while (channel > 0) {
		// 각 자릿수를 검사
		r = channel % 10;

		// 쓸 수 없는 값이면 false
		if (isBroken[r]) {
			return false;
		}

		// 검사한 자리 제거
		channel /= 10;
	}

	return true;
}

int main() {
	// 입력
	int n, m;
	std::cin >> n >> m;

	int temp = 0;
	for (int i = 0; i < m; i++) {
		std::cin >> temp;
		isBroken[temp] = true;
	}

	// 계산
	// 모든 숫자 버튼이 고장난 경우 +, -만 조작
	// 98 ~ 103번 채널은 +, -만 하는 게 더 이득
	if (m == 10 || (98 <= n && n <= 103)) {
		std::cout << abs(n - 100);
		return 0;
	}

	int answer;
	for (int i = 0; ; i++) {
		// + 버튼 조작
		if (n - i >= 0 && canMakeChannel(n - i)) {
			answer = countDigits(n - i) + i;
			break;
		}

		// - 버튼 조작
		if (canMakeChannel(n + i)) {
			answer = countDigits(n + i) + i;
			break;
		}
	}

	// +, -로 조작한 횟수보다 i가 커지면, +, -로 조작
	if (answer > abs(n - 100)) {
		answer = abs(n - 100);
	}

	std::cout << answer;
}

 

결과

시간은 비슷비슷

---

강평

문제 자체도 난이도가 꽤 있었고, 뭣보다 예외 처리가 상당했다. 풀고 나서도 다른 분들의 코드를 보며 많은 걸 배울 수 있었다. (1e5라던지)

 

그래서 꽤나 만족한 문제.

 

+)

코드를 다시 살펴보던 중, 개선 사항이 하나 더 보였다.

 

	if (m == 10 || (98 <= n && n <= 103)) {
		std::cout << abs(n - 100);
		return 0;
	}

 

바로 이 부분인데, 마지막에 abs(n - 100)과 answer를 비교하는 구문 때문에 98 <= n && n <= 103이 필요없어진 것이다.

 

그래서 저 조건을 제거하고 다시 코드를 돌려보았는데...

 

 

시간이 0 ms로, 매우 줄어들었다. 저런 형태의 조건식이 오버헤드가 큰 걸까...?