다이나믹 프로그래밍4 [코딩테스트/ 백준 알고리즘] BOJ.1463 : 1로 만들기(바텀업) (C++ 풀이) 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 자료구조 - int input : 입력 - int dp[] : dp 테이블 알고리즘 - 다이나믹 프로그래밍 - 재귀 사용한 탑다운 방식 - 점화식 : dp[i] = min(DP(i / 2), DP(i / 3), DP(i - 1)) + 1 코드 #include #include using namespace std; int main() { //입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int input = 0; int dp[.. 2022. 1. 18. [코딩테스트/ 백준 알고리즘] BOJ.1463 : 1로 만들기(탑다운) (C++ 풀이) 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 자료구조 - int input : 입력 - int dp[] : dp 테이블 알고리즘 - 다이나믹 프로그래밍 - 재귀 사용한 탑다운 방식 - 점화식 : dp[i] = min(DP(i / 2), DP(i / 3), DP(i - 1)) + 1 코드 #include #include using namespace std; int dp[1000001] = {0}; int DP(int input) { //중복 계산 방지 if(dp[input] != 0) { return dp[input]; } else { if(in.. 2022. 1. 18. [코딩테스트/ 백준 알고리즘] BOJ.2839 : 설탕배달 (바텀업) (C++ 풀이) 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 자료구조 - int sugar[5001] : DP 테이블 - int input : 입력 값 알고리즘 - 다이나믹 프로그래밍 - 반복을 통한 바텀업 방식 사용 - 점화식 : sugar[input] = min(DP(input - 5), DP(input - 3)) + 1 코드 - 두 수 중에 최솟값을 구하는 min() 함수를 구현하기 귀찮다면 C++에서 라이브러리를 추가하면 된다. 코드 #include.. 2022. 1. 17. [코딩테스트/ 백준 알고리즘] BOJ.2839 : 설탕배달 (탑다운) (C++ 풀이) 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 자료구조 - int sugar[5001] : DP 테이블 - int input : 입력 값 알고리즘 - 다이나믹 프로그래밍 - 재귀를 통한 탑다운 방식 사용 - 점화식 : sugar[input] = min(DP(input - 5), DP(input - 3)) + 1 코드 - 두 수 중에 최솟값을 구하는 min() 함수를 구현하기 귀찮다면 C++에서 라이브러리를 추가하면 된다. 코드 #include.. 2022. 1. 17. 이전 1 다음
