백준276 [Baekjoon] 15652 - N과 M (4) 📝 문제 🔑 풀이 과정 · 같은 수를 여러 번 골라도 된다 → 중복 허용, 방문 배열 필요 없음 · 비내림차순 수열: depth가 i일때의 수는 depth가 i-1때의 수보다 크거나 같다. 이를 처리하기 위해 현재 depth의 수를 인자로 넘겨주고, 함수 내에서 i보다 크거나 같은 범위를 탐색하게 한다. 🔓 답안 import java.io.*; import java.util.StringTokenizer; public class Main { static StringBuilder sb; static int N; static int M; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br =.. 2023. 7. 30. [Baekjoon] 15651 - N과 M (3) 📝 문제 🔑 풀이 과정 · 같은 수를 여러 번 골라도 된다 → 중복 허용, 즉 방문배열이 필요가 없다. 🔓 답안 import java.io.*; import java.util.StringTokenizer; public class Main { static StringBuilder sb; static int N; static int M; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWri.. 2023. 7. 29. [Baekjoon] 2579 - 계단 오르기 📝 문제 ❗ 주의 계단의 개수가 300이하의 자연수 이므로, 1도 가능하다. DP배열을 채우는 부분에서 인덱스 2에 접근할때가 있는데, 계단 개수가 1일때는 인덱스 초과 에러가 날 수 있다. 그래서 계단 개수가 1일때의 경우는 따로 처리를 해줬다. 🔑 풀이 과정 · DP를 사용해서 문제풀이를 진행한다. 이 문제는 DP배열을 2차원으로 선언해서 풀이했다. DP[i][0]: i-1칸에서 한 칸을 올라와서 i를 밟았을때의 최대 점수 DP[i][1]: i-2칸에서 두 칸을 올라와서 i를 밟았을때의 최대 점수 · 예제 1 풀이 · i가 3이상일때 DP[i][0]: 연속된 3칸을 밟을 수 없으므로, DP[i][1] + arr[i] DP[i][1]: DP[i-2][0] 와 DP[i-2][1] 중 큰 값을 선택한 후 .. 2023. 7. 28. [Baekjoon] 15486 - 퇴사 2 📝 문제 🔑 풀이 과정 14501 퇴사 문제는 N이 15로 작으므로 브루트포스로, 이 문제는 N이 1.5 * (10^6)으로 매우 크므로 다이나믹 프로그래밍(DP) 방식을 사용해서 풀이한다. · D[i]: i일부터 N+1일째까지 얻을 수 있는 최대 수익. 그리고 이 문제는 top-down 방식으로 풀이할 것이다. · 사실 14501과 알고리즘 자체는 거의 유사하다. 상담일수가 N+1을 넘으면 그 날 배정된 상담 자체가 불가능하다. 넘지않으면 그 날 배정된 상담을 택할수도 있고, 안할수도 있다. 택할때의 수익이 높은지, 안할때의 수익이 더 높은지를 비교해서 수익이 더 높을때를 배열에 넣어주면 되는것이다. · 풀이했던 과정(예제 1) · 사실 이 문제 풀이를 잘 모르겠어서 먼저 검색한 후 top-down으로.. 2023. 7. 27. [Baekjoon] 14501 - 퇴사 📝 문제 🔑 풀이 과정 우선 이 문제는 다이나믹 프로그래밍(DP) 문제로 유명하다. 그러나 나는 N이 15이하인 이 문제는 브루트 포스로 풀고, N이 1.5 * (10^6)인 퇴사 2 문제를 다이나믹 프로그래밍 방식으로 풀어보려 한다. (N말고 그 외는 다 똑같음) · DFS 방식을 활용해서 문제를 풀이할 것이다. 우선 메소드를 만드는데, 메소드의 인자는 (현재 날짜, 지금까지의 상담금액) 이렇게 두 가지를 사용한다. · 전체적인 알고리즘은 다음과 같다. 현재 날짜가 i일때, i일에 있는 상담 선택 가능 여부를 확인한다. (i + i일의 상담 소요 기간) 2023. 7. 26. [Baekjoon] 14889 - 스타트와 링크 📝 문제 🔑 풀이 과정 · 백트래킹을 사용하여 N/2개를 방문하고, 방문배열이 true인 팀과 방문배열이 false인 팀의 점수를 각각 구해서 그 차이를 구한다. · 택하는 방법은 조합을 이용하므로, 현재 택한 숫자보다 더 큰 부분을 탐색하게 만든다 (1, 3을 택하는 것과 3, 1을 택하는 것은 같으므로) · N/2를 택하는 것은 depth를 DFS의 변수로 넘겨서 체크한다. · 사실 맞힌 문제지만... 나에겐 좀 어렵다. 나는 DFS랑 백트래킹 같은 재귀방식이 아직 어렵다. 깊게 들어갔다가 다시 나올때 그 인덱스 변환이 너무 어렵다. · 그리고 사실 첫 제출때 시간초과를 받고 그 후 코드를 수정해서 정답처리를 받았다. 크게 바꾼것이 아니라, DFS인자에 현재 선택한 값을 넣어주고, 그 후 방문하지 않.. 2023. 7. 25. 이전 1 ··· 9 10 11 12 13 14 15 ··· 46 다음
