[백준 1107번] 리모컨

난이도: 골드 5

문제 링크: www.acmicpc.net/problem/1107

1107번: 리모컨

백준 1107번: 리모컨

처음에는 각 숫자 자리수별로 비교해서 가장 가까운 수를 찾는 방법으로 하려다가...

굉장히 비효율적이고 정확하지 않은 알고리즘이 완성되어서 (string으로 입력받은 N을 변환하는 등)

혹시...? 하고 접근해 본 브루트 포스 메소드로 성공적으로 푼 문제입니다.

 

아래와 같이 접근했습니다.

• 숫자 0~9에 대해, bool 타입의 isBroken array를 만듭니다. 입력받은 망가진 버튼들에 대해 true로 설정해 줍니다.
• 숫자 0~1,000,000까지 loop를 돌며, 다음을 수행합니다:
  • 모든 자릿수를 검사하여, 망가진 버튼을 하나라도 포함한다면 연산을 하지 않습니다.
  • 망가진 버튼을 하나도 포함하지 않는 수에 대해, 버튼을 누른 횟수 = 찾은 수 - 목표하는 채널 의 절댓값으로 합니다.
  • 버튼을 누른 횟수 + 찾은 수의 자릿수를 답으로 리턴합니다.
  • 100만까지 루프를 도는 이유는, 목표하는 채널보다 큰 수에서 시작하여 하강하며 접근할 때를 고려하기 위함입니다.

이 문제 이후로 백준에서 알고리즘 분류 표시 기능을 꺼 버리기로 했습니다.

평소에 백준에서 문제를 보고, 알고리즘 분류를 보고 나서 풀기 시작하는 게 언젠가 독이 될 수도 있겠다는 생각이 들었어요.