[백준] 1107번 리모컨 - 파이썬(Python)

2021. 9. 27. 13:46· 알고리즘/문제풀이
목차
  1. 문제 (링크)
  2. 나의 풀이
  3. 풀이법 및 코드 설명
728x90

문제 (링크)

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

 

1107번: 리모컨

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼

www.acmicpc.net

 

나의 풀이

import sys
input = sys.stdin.readline
target = int(input())
n = int(input())
broken = list(map(int, input().split()))

# 현재 채널에서 + 혹은 -만 사용하여 이동하는 경우
min_count = abs(100 - target)

for nums in range(1000001):
    nums = str(nums)
    
    for j in range(len(nums)):
        # 각 숫자가 고장났는지 확인 후, 고장 났으면 break
        if int(nums[j]) in broken:
            break

        # 고장난 숫자 없이 마지막 자리까지 왔다면 min_count 비교 후 업데이트
        elif j == len(nums) - 1:
            min_count = min(min_count, abs(int(nums) - target) + len(nums))

print(min_count)

풀이법 및 코드 설명

브루트포스 방식으로 모든 경우의 수를 탐색한다.

 

처음에는 고장나지 않은 숫자들로 만들 수 있는 모든 순열을 만들어주고, target과 가장 가까운 순열을 구해 두 숫자 사이의 차이를 구하고자 했다.

 

하지만, 순열을 만드는 과정에서 요소를 중복해서 뽑을 수 있어야하기 때문에 (Ex ) 5555 등..) 기존에 알고 있던 itertools.permutations를 사용할 수 없었다.

 

따라서, 모든 가능한 수에 대하여 해당 작업을 처리해주었다.

 

여기서 range를 N의 최대 범위인 500,000이 아닌 그 두 배 1,000,000로 해준 것은, 수빈이가 이동하려는 채널의 범위는 500,000 이하이지만 채널 자체는 무한대라는 점 때문이다.

 

따라서, target와 가장 가까운 숫자를 찾을 때 target보다 작은 값은 물론이고 target보다 큰 값도 찾아줘야하고, 이 값은 500,000 이상도 가능하다.

 

만약에 수빈이가 이동하려는 채널이 500,000이고, 리모컨의 숫자 중 1, 2, 3, 4, 5가 고장났다고 가정하자.

 

이 때, range의 범위가 500,000으로 제한되면, 시작점인 100번에서 +만 눌러서 500,000까지 도달하는 총 499,900번 버튼을 클릭하게 할 것이다.

 

하지만 물론 이것은 최적의 해가 아니다.

 

600,000에서 -를 100,000번 눌러 target에 도달하는 것이 최적의 해일 것이다.

 

이러한 이유 때문에 range는 1,000,000까지로 설정해주어야 한다.

저작자표시 (새창열림)

'알고리즘 > 문제풀이' 카테고리의 다른 글

[백준] 12865번 평범한 배낭 - 파이썬(Python)  (0) 2021.09.29
[백준] 2467번 용액 - 파이썬(Python)  (0) 2021.09.28
[백준] 1182번 부분수열의 합 - 파이썬(Python)  (1) 2021.09.26
[백준] 2110번 공유기 설치 - 파이썬(Python)  (0) 2021.09.23
[백준] 1958번 LCS 3 - 파이썬 (Python)  (0) 2021.09.21
  1. 문제 (링크)
  2. 나의 풀이
  3. 풀이법 및 코드 설명
'알고리즘/문제풀이' 카테고리의 다른 글
  • [백준] 12865번 평범한 배낭 - 파이썬(Python)
  • [백준] 2467번 용액 - 파이썬(Python)
  • [백준] 1182번 부분수열의 합 - 파이썬(Python)
  • [백준] 2110번 공유기 설치 - 파이썬(Python)
SeongOnion
SeongOnion
서버는 꺼지지 않아요
SeongOnion
조무래기 코딩
SeongOnion
전체
오늘
어제
  • 분류 전체보기 (167)
    • 알고리즘 (81)
      • 이론 (8)
      • 문제풀이 (73)
    • 언어 (15)
      • Python (9)
      • JavaScript (1)
      • JAVA (5)
    • 데이터베이스 (5)
    • 프레임워크 (15)
      • Django (7)
      • Spring (8)
    • 그 외 공부 (38)
      • 운영체제 (1)
      • 자료구조 (14)
      • 네트워크 (5)
      • CS (2)
      • 기타 (7)
      • 트러블 슈팅 (9)
    • 프로젝트 (0)
    • 개발자취 (8)
    • 회고 (3)
    • 주저리주저리 (1)
    • 기타 (비개발) (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • spring
  • 에라토스테네스의 체
  • 트러블 슈팅
  • 알고리즘
  • 백준
  • 프로그래머스
  • 소수
  • 이진탐색
  • 브루트포스
  • 회고
  • 장고
  • 자바
  • 개발자
  • DRF
  • Django
  • 웹
  • 컨트리뷰트
  • 파이썬
  • 큐
  • 그리디알고리즘
  • 코딩
  • 투 포인터 알고리즘
  • BFS/DFS
  • DP
  • 정렬 알고리즘
  • BFS
  • 코딩테스트
  • 스택
  • 오픈소스
  • 데이터베이스

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
SeongOnion
[백준] 1107번 리모컨 - 파이썬(Python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.