[BOJ/백준 코딩] 1로 만들기 - PYTHON #1463

소스 코드

n = int(input())

board = [0 for _ in range(n + 1)]

if n == 2:
    board[2] = 1

elif n > 2:
    board[2] = 1
    board[3] = 1
    for q in range(4, n + 1):

        # 2 or 3으로 나눠지는 경우
        if q % 2 == 0 or q % 3 == 0:
            temp = n

            # 2로 나눠지는 경우
            if q % 2 == 0:
                if temp > board[2] + board[q // 2]:
                    temp = board[2] + board[q // 2]

            # 3으로 나눠지는 경우
            if q % 3 == 0:
                if temp > board[3] + board[q // 3]:
                    temp = board[3] + board[q // 3]

            # 빼기 1 하는 경우
            if temp > board[q - 1] + 1:
                temp = board[q - 1] + 1

            board[q] = temp

        # 2,3으로 나눠지지 않는 경우
        else:
            board[q] = board[q - 1] + 1

print(board[n])

 

---

해결 방법

1. dp로 진행 ( bfs 시간초과 )

 

2. n짜리 배열 만들고, 배열에 1만들 수 있는 최소 횟수 저장 ( 2,3번째 자리에 1 넣기(1로 갈 수 있는 최소 횟수) )

- 2,3으로 나눌 수 없는 값 = 홀수 > 홀수 - 1 = 2의 배수(3의 배수도 가능) > 현재 위치 - 1 위치에 있는 값 + 1(3번 연산) 

ex) 10의 경우, 2*5로 표현 가능 > 1+3 = 4, (10 - 1)//3으로 표현 가능 > 2(9번 인덱스의 값) + 1(3번 연산)

> min(4,3) == 3으로 나옴

1	2	3	4	5	6	7	8	9	10
0	1	1	2	3	2	3	3	2	3

 

3. 2 or 3 으로 나눌 수 있는 경우와 없는 경우

 

3-1. 2 or 3 으로 나눌 수 있는 경우

- 1,2,3번 연산 모두 확인 후, 가능한 것들의 최소값 찾기

 

3-2. 2 or 3 으로 나눌 수 없는 경우

- 3번 연산으로 최소값 찾기

---

느낀 점

 

 

ps. 개인적인 코드와 코드를 작성의 이유를 적은 것입니다.

 

오류나 적절치 않은 문법이 존재할 수 있으며, 다른 분들께는 굉장히 비효율적인 방법으로 여겨질 수 있습니다.

 

혹시 개선 사항, 오류 및 문제에 대한 수정 사항 등을 댓글로 남겨주신다면 감사한 마음으로 배우고 수정하겠습니다.