본문 바로가기

Programming/Baekjoon3

[백준] 1003번 - 피보나치 함수 (JAVA) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 문제는 fibonacci(N)을 호출했을 때 0과 1이 출력되는 횟수를 각각 구해야 하기 때문에 0과 1의 경우를 나누어 저장해야합니다. 따라서 dp 테이블을 2차원 배열로 하여 dp[i][0] 은 fibonacci(i)를 호출했을 때 0이 출력되는 횟수, dp[i][1]는 fibonacci(1)을 호출했을 때 1이 출력되는 횟수로 합니다. 따라서 dp[0][0] = 1, dp[1][1] = 1이 됩니다. 피보나치 수열을 dp로 푸는 방법을 간단하게 설명해보겠습니다. 피보나치 수열을.. 2023. 6. 3.
[백준] 9095번 - 1, 2, 3 더하기 (JAVA) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 가능한 연산은 1을 더하기, 2를 더하기, 3을 더하기 3가지입니다. 1은 [1] 로 1가지, 2는 [1+1, 2]로 2가지, 3은 [1+1+1, 2+1, 1+2, 3]으로 4가지, ... 등으로 나올 것입니다. dp 테이블에는 i를 1, 2, 3을 더하여 만들 수 있는 경우의 수가 들어갈 것입니다. i를 만들기 위해서는 i-1에 1을 더하기, i-2에 2를 더하기, i-3에 3을 더하기 3가지 경우가 있습니다. 따라서 dp[i]는 3가지 경우를 모두 합한 값이 될 것입니다. 이를 점.. 2023. 6. 3.
[백준] 1463번 - 1로 만들기 (JAVA) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 💭 문제 💬 풀이 Bottom-Up 방식으로 반복문을 이용해서 풀었습니다. 먼저 가능한 연산은 1) 3으로 나누기, 2) 2로 나누기, 3) 1을 빼기 3가지 경우로, 이 문제는 3가지 연산을 이용해서 N을 1로 만들 수 있는 최소한의 연산 횟수를 구하는 문제입니다. 여기서 주의해야 할 점은 단순히 큰 수로 연산하는 것이 최소 연산 횟수를 구할 수 있는 것은 아니라는 점입니다. 예를 들어 10의 경우, 연산 가능한 큰 수로 연산하면 10 -> 5(2로 나눔) -> 4(1을 뺌) -> 2(2로 나눔) -> 1(2.. 2023. 6. 3.

티스토리툴바