nonneng.ee
Daeun-rithm
nonneng.ee
전체 방문자
오늘
어제
  • 분류 전체보기 (51)
    • Back-end (17)
      • Server (3)
      • Database (3)
      • Spring (9)
      • Node.js (1)
    • Book (1)
      • 이펙티브 자바 (0)
      • 대규모 시스템 설계 (1)
    • Algorithm (1)
      • Greedy, Implementation (6)
      • Dynamic Programming (5)
      • Data Structure (3)
      • Sorting (2)
      • Concept (1)
    • TIL (11)
    • Software (3)
      • Design Pattern (3)
    • Computer Science (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • node js
  • 아이템8
  • Java
  • 구현
  • Restful API
  • jwt
  • JPA
  • 소스설치
  • MySQL
  • 파이썬
  • 서버
  • APM
  • 수동설치
  • 브루트포스
  • Spring
  • 에러
  • 자바
  • 아이템 25
  • 이펙티브 자바
  • 컴파일설치
  • API
  • Postman
  • 우분투
  • 아이템9
  • 구동원리
  • DP
  • 아이템6
  • 백준
  • 아이템 23
  • 가상머신

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
nonneng.ee

Daeun-rithm

Algorithm/Dynamic Programming

[Java] 백준 #1463 1로 만들기

2022. 7. 18. 12:05

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

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

정수 X에 사용할 수 있는 연산 세 가지를 적절히 사용해서 정수 N을 1로 만든다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

연산 사용 횟수의 최솟값 구하기

💡 알고리즘

다이나믹 프로그래밍

💡 접근

RGB거리처럼 모든 케이스의 계산횟수가 동일한 문제가 아니므로, 배열만으로는 해결하기 어려울 것 같다.

→ 재귀함수를 작성하고, 전역변수를 통해 최솟값을 관리하자.

💡 코드

package DP;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1463 {

    // 재귀함수 <-> 전역변수로 리턴값 관리
    static int res = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        recur(N, 0);
        System.out.println(res);
    }

    static void recur(int num, int cnt){
        // else if문을 쓰면 안됨 !!!!
        if (num == 1){
            res = Math.min(res, cnt);
        }
        if(cnt >= res){
            return;
        }
        if(num % 3 == 0){
            recur(num / 3, cnt + 1);
        }
        if(num % 2 == 0){
            recur(num / 2, cnt + 1);
        }
        recur(num - 1, cnt + 1);
    }
}

💡 정리

  • 재귀함수 작성 + 전역변수 관리
  • 가능한 모든 경우에 대하여 함수를 호출해야 하므로, else if문을 사용하면 안된다⭐

'Algorithm > Dynamic Programming' 카테고리의 다른 글

[Algorithm/Java] 다이나믹 프로그래밍 복습  (0) 2022.07.14
[Python] 백준 #11052 카드 구매하기  (0) 2021.06.30
[Python] 백준 #1932 정수 삼각형  (0) 2021.06.30
    'Algorithm/Dynamic Programming' 카테고리의 다른 글
    • [Algorithm/Java] 다이나믹 프로그래밍 복습
    • [Python] 백준 #11052 카드 구매하기
    • [Python] 백준 #1932 정수 삼각형
    • [Python] 백준 #1149 RGB거리
    nonneng.ee
    nonneng.ee

    티스토리툴바