목록2025/01 (2)
멍두의 개발새발
[백준] 1로 만들기 in Java
📍 문제https://www.acmicpc.net/problem/1463 정수 N이 주어졌을 때 1. 3으로 나누거나2. 2로 나누거나3. 1로 빼서가장 적게 연산을 하여 1로 만드는 횟수를 구하는 문제이다. bfs로 /3 /2 -1해서 가장 빨리 1에 도착하는 방법으로도 풀 수 있을 것 같다.하지만 좀만 고민해본다면 dp로 풀 수 있고 dp가 시간 복잡도 깡패이므로 dp로 풀겠다.📍 코드 설명n=1일 때 : 0이다n=2일 때 : 2/2를 하면 1이므로 1이다n=3일 때 : 3/3을 하면 1이므로 1이다n=4일 떄 : 4/2 = 2, 2/2 = 1이므로 2이다n=5일 때 : 5-1 = 4, 4/2 = 2, 2/2=1 이므로 3이다n=6일 떄 : 6/3 = 2, 2/2 = 1이므로 2이다.n=7일 때 ..
Algorithm/BOJ
2025. 1. 31. 17:26
