[백준/JAVA] 1463번: 1로 만들기
🔺 문제
1463번: 1로 만들기
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
www.acmicpc.net
🔺 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int D[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
D = new int[N + 1];
D[1] = 0;
for(int i = 2 ; i <= N ; i++) {
D[i] = D[i - 1] + 1; // 🔔 -1 먼저 하기
if(i % 2 == 0) D[i] = Math.min(D[i], D[i/2] + 1); // % 2 연산
if(i % 3 == 0) D[i] = Math.min(D[i], D[i/3] + 1); // % 3 연산
}
System.out.println(D[N]);
}
}
|
cs |
✅ 해결 아이디어
✔ DP - 점화식 (Bottom-Up 방식)
→ D[i] : i에서 1로 만드는 데 걸리는 최소 연산 횟수
💥 유의사항
⇨ DP문제에서는 초기값 설정하는 거 잊지 말기!
⇨ DP 문제 해결 과정
1) 테이블 정의하기
2) 점화식 찾기
3) 초기값 설정하기
🔺 다른 풀이들
- 멋진 풀이.. 감사합니다.. (복습용)
[알고리즘-JAVA] 백준 알고리즘 1463번 - 1로 만들기
접근 과정 1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은? 임의의 숫자 (10^6보다 작음) 가 주어지면, 그 숫자를 3으로 나누거나 2로 나누거나 1을 빼서 1로 만드는 문제이다. 2. 나의 방식
odysseyj.tistory.com
- 점화식 찾는 과정까지... 👍👍 (복습용)
[백준] 1463번 1로 만들기 - Java, 자바
실버 3 DPhttps://www.acmicpc.net/problem/1463DP 문제를 풀 땐 3가지 단계를 생각한다.1\. 테이블 정의 2\. 점화식 찾기3\. 초기값 정하기 문제에 적용해보자.테이블 정의Di = 정수가 i를 1로 만들때 연산을 하
velog.io
[백준/1463/Java] 1로 만들기 - DP 풀이
문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제를 먼저 풀고 오시는 것을 추천합니다. 이 문제의 풀이는 DP(Dy
smartpro.tistory.com
- 6으로 나눠지는 경우까지 생각해서 푸심
[백준] 1463번 : 1로 만들기 – JAVA [자바]
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 문제 풀이 백준 1463번 1로 만들기는 실버 3 난이도의 DP 문제
propercoding.tistory.com
💬 느낀 점
점화식 이제부터 시작이야~~
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 230705 | 240309 |
(참고)
✔ Do it 알고리즘 코딩테스트 자바편