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
개인 공부 / 정리 블로그입니다
  • seulll
    seulll
    seulll
  • 전체
    오늘
    어제
    • 분류 전체보기 (336) N
      • 코딩테스트 (228) N
        • programmers (python) (156)
        • 백준 (python) (70) N
      • 자료구조 | 알고리즘 (14)
      • 개발 | 프로젝트 (43) N
        • Python (4)
        • Java | Spring (7)
        • Android (5) N
        • Unity (3)
        • API (4)
      • CS (15)
        • Network (5)
        • SQL (2)
        • OS (4)
      • 데이터 분석 (14)
      • 기타 (13)
  • 블로그 메뉴

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

    • GitHub
  • 인기 글

  • 태그

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

  • 최근 글

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

티스토리툴바