본문 바로가기

DP40

[백준] 1351번 : 무한 수열 – JAVA [자바] https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 문제 문제 풀이 백준 1351번 무한 수열은 골드 5 난이도의 DP 및 해시 문제이다. 이 문제 자체는 되게 간단하다. 3개의 정수 N, P, Q가 주어지고 아래에 있는 공식을 써서 An을 구하면 된다. 이 문제에서는 참고해야 할 게 있다. 우선 정수 N의 범위 0 ≤ N ≤ 10^12이다. 즉, 이 범위는 long 형이고 자바에서는 배열이 long 형인 크기로 만들지 못한다. 자세한 이유는 이 링크를 참고하면 되겠다. 즉, 값들을 배열에 저장을 할 수가 없기 때문에 해시맵에 저장해야 한다. 추가로, 이 문제는 Bottom-Up 방식을 이.. 2023. 7. 16.
[백준] 2748번 : 피보나치 수 2 – JAVA [자바] https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 문제 풀이 백준 2748번 피보나치 수 2는 브론즈 1 난이도의 수학 및 DP 문제이다. 이 문제에서는 정수 N이 주어진다. 이때 N번째 피보나치 수를 출력하면 된다. 이 문제는 재귀 함수를 이용해서도 풀 수 있겠지만 더 효율적인 DP(다이나믹 프로그래밍)을 이용해서 풀 것이다. DP가 재귀 함수보다 더 효율적인 이유는 재귀 함수로 풀면 풀었던 것을 반복해.. 2022. 8. 14.
[백준] 1003번 : 피보나치 함수 – JAVA [자바] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 문제 풀이 백준 1003번 피보나치 함수는 실버 3 난이도의 DP 문제이다. 이 문제에서는 피보나치의 소스 코드가 C++ 언어로 작성되어 있다. 이 소스 코드는 밑에서 볼 수 있다. //피보나치 소스 코드 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } 이 소.. 2022. 7. 11.
[백준] 9095번 : 1, 2, 3 더하기 – JAVA [자바] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 문제 풀이 백준 9095번 1, 2, 3 더하기는 실버 3 난이도의 DP 문제이다. 이 문제에서는 테스트 케이스의 개수 T가 주어진다. 그리고 각 테스트 케이스마다 정수 n이 주어진다. 이때 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력하면 된다. 우선 예를 들어보겠다. n = 1 1 ∴ 1가지 n = 2 1 + 1 2 ∴ 2가지 n = 3 1 + 1 + 1 1 + 2 2 + 1 3 ∴ 3가지 n = 4 1 + 1 + 1 + 1 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2.. 2022. 7. 11.
반응형

티스토리툴바