다이나믹 프로그래밍, 비트마스킹 문제입니다. 0~9까지 숫자를 전부 사용한 계단 수의 개수를 찾아야 합니다. 계단 수는 앞과 뒤가 1차이나는 숫자로 0부터 시작할 수 없습니다. 0~9까지의 숫자를 사용했는지에 대해서 비트마스킹을 사용합니다. 10개의 숫자이므로 (1
다이나믹 프로그래밍 문제입니다. 상담을 적절히 해서 최대 수익을 구해야 합니다. 매일 상담은 한 건이 있으며 해당 상담에 대하여 시간과 값이 주어집니다. 뒤에서부터 탐색하여 해당 상담이 가능한지 확인합니다. 그리고 다음의 점화식을 사용합니다. dp[i] = Math.max(value[i] + dp[i + time[i] + 1], dp[i + 1]); 아래 두개를 비교해서 큰 값을 현재 날짜의 최대 값으로 저장합니다. 1. 현재 위치의 값 + 현재 상담을 마무리 했을 때 다음 상담으로 얻을 수 있는 최대값 2. 내일 얻을 수 있는 최대 값 (오늘 상담을 하지 않는 경우) import java.io.BufferedReader; import java.io.BufferedWriter; import java.io..
다이나믹 프로그래밍 문제입니다. 판다가 작은 나무에서 많은 나무로만 이동할 때 최대 이동 수를 찾아야 합니다. 모든 위치에 대해서 x, y, value값을 저장한 배열을 만들어 주었습니다. 오름차순으로 정렬하고 차례대로 탐색합니다 탐색하는 위치의 상하좌우를 확인하고 아래의 점화식을 사용해줍니다. if (map[nextY][nextX] > map[al.get(i).y][al.get(i).x]) { dp[nextY][nextX] = Math.max(dp[nextY][nextX], dp[al.get(i).y][al.get(i).x] + 1); } 현재 위치가 다음위치(상하좌우) 보다 작을 때 (이동 가능한 곳 일 때) 저장되어 있는 값과 현재위치에 저장된 값 + 1 중 큰값으로 DP배열에 저장합니다. 위의 과..
다이나믹 프로그래밍 문제입니다. 알약을 먹는 규칙이 있을 때 가능한 경우의 수를 출력해야 합니다. 알약을 먹는 규칙은 다음과 같습니다. 1. 알약 하나를 반으로 쪼개서 반은 먹고 반은 다시 통에 담는다. 2. 반으로 쪼개진 알약 이라면 그대로 먹는다. DP를 적용하기 위해 반복되는 부분이 무엇인지 찾아봅니다. 알약이 A개, 반쪽 알약이 B개 일 때 알약을 꺼내서 반으로 쪼개서 먹거나 => (A-1) (B+1) 반쪽 알약을 꺼내서 먹는 경우로 => (A) (B-1) 이는 재귀 함수로 들어가게 됩니다. 위의 과정이 반복되고 똑같은 연산을 계속해서 처리하게 됩니다. 이를 DP로 처리해주기 위해서 알약A개, 반쪽 알약B개일 때 계산된 결과값을 저장해두었다면 다음 번에 재사용할 수 있습니다. 그래서 DP[알약 개..
이항계수 문제입니다. nCr로 입력받으며 이는 아래 코드로 구할 수 있습니다. for (int i = 0; i < r; ++i) { a *= (n - i); b *= (r - i); } 위의 코드에서 모듈러 연산을 추가해주어야 합니다. 그리고 구해진 값에서 a/b를 해야하는데 나눗셈을 하게 될 경우 모듈러 연산의 결과가 틀려지게 됩니다. 그래서 페르마 소정리를 통해서 계산해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Mai..
이항계수 문제입니다. nCr로 입력받으며 이는 아래 코드로 구할 수 있습니다. for (int i = 0; i < r; ++i) { a *= (n - i); b *= (r - i); } 위의 코드에서 모듈러 연산을 추가해주어야 합니다. 그리고 구해진 값에서 a/b를 해야하는데 나눗셈을 하게 될 경우 모듈러 연산의 결과가 틀려지게 됩니다. 그래서 페르마 소정리를 통해서 계산해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Mai..
이항계수 문제입니다. nCr로 입력받으며 이는 아래 코드로 구할 수 있습니다. for (int i = 0; i < r; ++i) { a *= (n - i); b *= (r - i); } 위의 코드에서 모듈러 연산을 추가해주어야 합니다. 그리고 구해진 값에서 a/b를 해야하는데 나눗셈을 하게 될 경우 모듈러 연산의 결과가 틀려지게 됩니다. 그래서 페르마 소정리를 통해서 계산해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Mai..
이항계수 문제입니다. nCr로 입력받으며 이는 아래 코드로 구할 수 있습니다. for (int i = 0; i < r; ++i) { a *= (n - i); b *= (r - i); } 위의 코드에서 모듈러 연산을 추가해주어야 합니다. 그리고 구해진 값에서 a/b를 해야하는데 나눗셈을 하게 될 경우 모듈러 연산의 결과가 틀려지게 됩니다. 그래서 페르마 소정리를 통해서 계산해주었습니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Sol..