1107 리모컨

1107 리모컨 (c++)

문제

https://www.acmicpc.net/problem/1107

접근 방식

브루트 포스

1. 처음엔 N을 문자열로 받아서 N과 가까운수 중 눌릴 수 있는 수를 찾아보려고 했다.
   • (N[i]가 5인데 5가 안눌리면 4, 6 이런식)
2. 그런데 그럼 2555에서 2가 안눌리면 3555, 1555가 나온다
   • (가까운 수를 찾으려면 3000, 1999가 나와야함)
3. 그래서 첫째수가 같으면 그 뒤로도 최대한 비슷한 수가 나오게하고, 첫째수가 원래수보다 낮으면 높은수, 높으면 낮은수를 찾아보려고 했다.
   • (234일 때 첫째수가 1이면 뒤에는 최대한 9에 가깝게, 3이면 뒤에는 최대한 0에 가깝게)
4. 그런데 이 조건에 맞춰서 코딩한다는게 되게 애매했다.
5. 결국 못풀고 분류를 봤고 브루트포스라는걸 알게됐다.
6. 1~1’000’000까지 다 해보면서 최소값을 출력했다 (성공)
7. 54ms인가 나왔는데 상위권은 죄다 0ms였다. (더 최적화시킬 방법이 있다.)
8. 찾아보니 N 부터 시작해서 N - 1, N + 1, N - 2, N + 2 이런식으로 점차 늘려가는거였다. (그리디?)
   • 이 때 - 를 먼저하는게 중요하다 (빠지면 자릿수가 줄어들어서 누를 버튼의 수가 줄어들게 된다.)
9. 적용해서 0ms 에 해결했다. (109위)

문제 풀이

#include <iostream>
#include <string>
using namespace std;

int N, M;

bool btn[10] = {};

inline int Abs(int a) { return a > 0 ? a : a * -1; }
inline int Min(int a, int b) { return a < b ? a : b; }

bool IsPressable(int num)
{
	if (num < 0) return 0;
	if (!num) return !btn[0];
	while (num > 0)
	{
		if (btn[num % 10]) return 0;
		num /= 10;
	}
	return true;
}

int main()
{
	cin >> N >> M;

	if (M == 10)
	{
		cout << Abs(100 - N) << endl;
		return 0;
	}

	while (M-- > 0)
	{
		int temp;
		cin >> temp;
		btn[temp] = 1;
	}

	for (int i = 0; i < 500'001; ++i)
	{
		if (IsPressable(N - i)) { cout << Min(i + to_string(N - i).size(), Abs(100 - N)) << endl; break; }
		if (IsPressable(N + i)) { cout << Min(i + to_string(N + i).size(), Abs(100 - N)) << endl; break; }
	}

	return 0;
}

다시 생각해볼 점

1. 우선 기본 접근을 항상 브루트포스부터 해봐야한다. (문제의 기본 구조를 알기 위해서라도)
2. 입출력이 많지 않을 때는 굳이 cin.tie cout.tie 등을 쓸 필요가 없다.
3. 간단한 abs, min, max 등은 inline 함수로 직접 만들어서 사용하자 (자료형을 정해놓고 만들기때문에 훨씬 빠름)
4. static_cast(str.length()) 같은 멍청한 짓을 하지 말고 str.size()를 쓰짜
5. 세상엔 정말 우아하게 코드를 짜는 사람들이 많다.

참조

https://yjios.tistory.com/8
https://www.acmicpc.net/source/24693857