DP(2)
-
[백준] 1463 1로 만들기
맨 처음에는 0.1초가 나오도록 값을 입력받으면 바로 해결하는 프로그램을 짜려고 했는데, 이것은 조금 힘들 거 같아서 dp로 생각을 돌렸다. 맨 처음에는 1을 뺀 배열의 값을 참조해서 1을 더해주고 두번짼는 2로 나눠지면 2로 나눠진 배열에 1을 더해주고 마지막에는 3으로 나눠지면 3으로 나눠진 배열에 1을 더해준다. 고려하는 순서가 -1 , /2, /3인 이유는 큰 수를 나눌수록 가장 작은 횟수를 찾을 수 있기 때문이다. #include using namespace std; int arr[1000001]; int main() { int n; cin >> n; for (int i = 2; i = arr[i / 2] + 1) { arr[i] = arr[i / 2] + 1; } } if (i % 3 == 0..
2022.06.28 -
백준 다리놓기 1010 C++
우선 먼저 했던 코드부터 올려보자면 #include #include #include #pragma warning(disable:4996) using namespace std; int main() { int t = 0; cin >> t; for (int i = 0; i > a >> b; vector b_b; a = min(a, b-a); unsigned long long int sum = 1; for (int q = 1; q = 1; u--) { sum = sum * b; for (int k = 0; k < a; k++) { if (sum% b_b[k] == 0 && b_b[k] != 1) { sum = sum / b_b[k]; b_b[k] = 1; } } ..
2021.11.26