Programmers / 2단계 / 숫자 변환하기 / python

2024. 3. 22. 01:25·코딩테스트/programmers (python)

 

코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr)

 

 

나의 풀이 (실패)

문제는 쉬워보였지만 막상 적절한 접근 방법이 떠오르지 않았다.

def solution(x, y, n):
    num=[]
    count=0
    x1=x; x2=x; x3=x
    
    while x3<y:
        x1+=n
        x2*=2
        x3*=3
        num.append(x1)
        num.append(x2)
        num.append(x3)
        count+=1
        
        if y in num:
            return count
            
    return -1

 

모범 답안

def solution(x, y, n):
    answer = 0
    dp = set()
    dp.add(x)
    
    while dp:
        if y in dp:
            return answer
        else:
            dp_y = set()
            for i in dp:
                if i+n <= y:
                    dp_y.add(i+n)
                if i*2 <= y:
                    dp_y.add(i*2)
                if i*3 <= y:
                    dp_y.add(i*3)
            dp = dp_y
            answer += 1
            
    return -1

 

dp를 활용한 문제였다.
x를 y로 변환하기 위한 최소 연산의 수가 필요하기 때문에 set 을 활용했다.

  1. x 값을 dp에 우선 대입한다.
  2. y 가 dp에 있다면, 정답을 리턴
  3. dp를 돌면서, i+n i*2 i*3 3가지 연산 중 y보다 작거나 같으면 dp_y라는 set에 add한다.
  4. 3번 연산을 마친 dp_y에 dp를 copy하면서 (answer+1)하면서 1~3 과정을 반복한다.

 

참조

프로그래머스 - 숫자 변환하기 (velog.io)

 

프로그래머스 - 숫자 변환하기

문제 설명 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다. x에 n을 더합니다 x에 2를 곱합니다. x에 3을 곱합니다. 자연수 x, y, n이 매개변수로 주어질 때, x를 y로

velog.io

 

'코딩테스트 > programmers (python)' 카테고리의 다른 글

Programmers / 3단계 / 최고의 집합 / python  (0) 2024.03.23
Programmers / 2단계 / 택배상자 / python  (0) 2024.03.22
Programmers / 2단계 / 롤케이크 자르기 / python  (0) 2024.03.19
Programmers / 3단계 / 이중우선순위큐 / python / heapq  (0) 2024.03.18
다익스트라(dijkstra) 알고리즘 파이썬 구현 코드  (1) 2024.03.18
'코딩테스트/programmers (python)' 카테고리의 다른 글
  • Programmers / 3단계 / 최고의 집합 / python
  • Programmers / 2단계 / 택배상자 / python
  • Programmers / 2단계 / 롤케이크 자르기 / python
  • Programmers / 3단계 / 이중우선순위큐 / python / heapq
seulll
seulll
개인 공부 / 정리 블로그입니다 https://github.com/seul1009
  • seulll
    seulll
    seulll
  • 전체
    오늘
    어제
    • 분류 전체보기 (344) N
      • 코딩테스트 (236) N
        • programmers (python) (158) N
        • 백준 (python) (76) N
      • 자료구조 | 알고리즘 (14)
      • 개발 | 프로젝트 (43)
        • Python (4)
        • Java | Spring (7)
        • Android (5)
        • Unity (3)
        • API (4)
      • CS (15)
        • Network (5)
        • SQL (2)
        • OS (4)
      • 데이터 분석 (14)
      • 기타 (13)
  • 블로그 메뉴

    • 홈
    • 태그
    • 글쓰기
    • 설정
  • 링크

    • GitHub
  • 인기 글

  • 태그

    대입 표현식
    데이터분석
    kakao map api
    티스토리챌린지
    웹크롤링
    백엔드 개발자 역량
    코딩테스트
    백엔드
    프렌즈4블록
    train_test_split
    그리디 알고리즘
    confusion matrix
    Boxplot
    파이썬
    오차행렬
    API
    asterisk
    카카오맵
    solving environment
    2 x n 타일링
    박스플롯
    Python
    바다코끼리
    야근 지수
    모델 성능 평가
    프로그래머스
    백엔드 개발자
    오블완
    카카오맵 api
    Greedy
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
seulll
Programmers / 2단계 / 숫자 변환하기 / python
상단으로

티스토리툴바