FilesExpand file tree

 master

/

5.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

30 lines (24 loc) · 991 Bytes

 master

/

5.java

Copy path

Top

File metadata and controls

• Code
• Blame

30 lines (24 loc) · 991 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

import java.util.*;

public class Main {

// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화

public static int[] d = new int[30001];

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int x = sc.nextInt();

// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)

for (int i = 2; i <= x; i++) {

// 현재의 수에서 1을 빼는 경우

d[i] = d[i - 1] + 1;

// 현재의 수가 2로 나누어 떨어지는 경우

if (i % 2 == 0)

d[i] = Math.min(d[i], d[i / 2] + 1);

// 현재의 수가 3으로 나누어 떨어지는 경우

if (i % 3 == 0)

d[i] = Math.min(d[i], d[i / 3] + 1);

// 현재의 수가 5로 나누어 떨어지는 경우

if (i % 5 == 0)

d[i] = Math.min(d[i], d[i / 5] + 1);

}

System.out.println(d[x]);

}

}