본문 바로가기

백준98

백준 1463번 : 1로 만들기 문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 구현 방법 dp로 풀어주었습니다. 1부터 시작하여 횟수의 최솟값을 구해주었습니다. 모든 값이 할 수 있는 연산인 -1을 dp 에 넣고 /2가 가능하면 /2의 값과 현재 -1을 한 dp 값을 비교하여 더 작은 값을 dp에 넣어줍니다. /3도 마찬가지로 비교하여 더 작은 값을 dp에 넣어줍니다. 구현 코드 package BOJ.Silver; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav.. 2021. 3. 19.
백준 9461번 : 파도반 수열 문제 www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 구현 방법 점화식을 구해준 다음 dp로 구현하였습니다. 그림을 보면 점화식은 dp[i] = dp[i-2] + dp[i-3] 임을 알 수 있습니다. 구현 코드 package BOJ.Silver; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ9461_파도반수열 { p.. 2021. 3. 19.
백준 9095번 : 1, 2, 3 더하기 문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 구현 방법 점화식을 구해준 다음 bottom-up 방식으로 반복문을 돌려 구해주었습니다. n이 1일 때 1, n이 2일 때 2, n이 3일 때 4, n이 4일 때 7이므로 n일 때 dp[n] = dp[n-1]+dp[n-2]+dp[n-3] 임을 알 수 있습니다. 구현 코드 package BOJ.Silver; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ909.. 2021. 3. 19.
백준 1010번 : 다리 놓기 문제 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 구현 방법 다리 구하는 개수는 조합을 사용하여 풀어줄 수 있습니다. 예제를 예를 들어 13 29가 입력 되었을 때 29C13을 구해주면 됩니다. 수가 너무 크므로 BigInteger 클래스로 dp 배열을 생성했습니다. dp에 31까지의 곱셈을 구해준 다음 dp[29] / dp[M-N = 17] 를 구해주면 29부터 17까지의 곱셈을 구할 수 있습니다. 이를 dp[13]으로 나누어주면 29C13의 값이 출력.. 2021. 3. 19.

티스토리툴바