전체 글
-
10844 쉬운 계단 수백준/DP 다이나믹 프로그래밍 2024. 8. 7. 21:39
아래 표에서,dp[i][j] : j가 맨 뒤에 올 때의 계단수 개수i = 1 일 때 계단수는,j0123456789계단수 x123456789dp[1][j]0111111111 i = 2 일 때 계단수는, j0123456789계단수 1021123223433454456556766787789889dp[2][j]1122222221 dp[2][4] 에서 j = 4 이고,이때의 계단수인 34, 54는 (j-1) 4 , (j+1)4 이므로,dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이다.즉, dp[2][4] = dp[1][3] + dp[1][5] = 1 + 1 = 2 이다.즉,길이가 2인 맨 끝에 4가 올 때의 계단수 개수= 길이가 1인 맨 끝에 3이 올 때의 계단수 개수 + 길이가 1인..
-
10986 나머지 합백준/누적 합 2024. 8. 4. 16:00
예제를 가지고 설명해보면 5 31 2 3 1 2 누적합을 통해서 문제를 풀 수 있다.특히 누적합%M 값을 이용한다. i01234입력값12312누적합13679누적합%M = A[i]10010 우리는 A[i] 값을 이용하는데, 정답으로 출력할 건수를 생각해보면, 1) A[i] = 0 인 부분i = 1,2,4 인 경우이다.각각 누적합이 3,6,9인 경우로 M(=3) 으로 나누면 나머지가 0 이므로 정답이 된다. 1-1)누적합이 3인 경우 : i = 0 부터 i = 1 까지의 합,누적합이 6인 경우 : i = 0 부터 i = 2 까지의 합누적합이 9 인 경우 : i = 0 부터 i = 4 까지의 합 즉, 3가지 경우가 있다. 1-2) 다른 경우도 생각해 볼 수 있다.i = 1,4의 경우를 생각하면,A[4]..
-
1806 부분합백준/두 포인터 2024. 8. 2. 23:28
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); int N = Integer.parseIn..
-
3151 합이 0백준/두 포인터 2024. 8. 2. 21:10
[ 1 ]예제를 한 경우 생각해보면,-5 -5 1 1 1 1 4 4 4 4 4 1) 주어진 예제에서 학생들의 코딩 실력을 오름차순 정렬한다.-5 -5 1 1 1 1 4 4 4 4 4 2) for 문을 돌리는데 투포인터도 같이 사용한다. (left, right) 2-1) i = 0 , left =1, right = 10즉, 0번째 값 = -5 , left = i+1 = 1-> 1번째 값 = -5 right = N-1 = 10-> 10 번째 값 = 4 이 때 세가지 경우의 합 = (-5) + (-5) + 4 = -6이 경우는, 0을 만들기에 더 작은 값이므로 left 를 증가시켜서 다시 합을 구한다. 2-2) i = 0 , left =2, right = 100번째 값 = -5 ,left = 1 +1 =..
-
14426 접두사 찾기백준/이분탐색 2024. 7. 30. 22:57
입력 예시 5 10 baekjoononlinejudge startlink codeplus sundaycoding codingsh baekjoon star start code sunday coding cod online judge plus 입력으로 주어진 N개의 문자열을 오름차순 정렬한 뒤,-> baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding 이분탐색으로 M개의 문자열이 접두사인지 여부를 파악하면 된다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util...
-
1508 레이스백준/이분탐색 2024. 7. 29. 22:51
가장 가까운 심판의 거리가 최대가 될 곳을 파악해야 한다. 11 2 40 5 10 11이 예제에서 생각해보면,최대 심판을 2곳에 위치시킬 수 있다. 1) 첫 번째 심판의 위치일단, 문제에서 정답이 여러개일 경우 사전순으로 가장 늦는 것을 출력하라고 했으므로,일단 0의 위치에 심판을 위치시킨다. 심판 위치 상태1 2) 두 번째 심판의 위치 최대 2곳에 심판을 위치시킬 수 있으므로 한 곳을 더 찾아야 한다. 2-1) 5에 위치 시킴 심판 위치 상태1 1 0 0 -> 가장 가까운 심판의 거리는 5-0 = 5 이다. 2-2) 10에 위치 시킴 심판 위치 상태1 0 1 0 -> 가장 가까운 심판의 거리는 10-0 = 10 이다. 2-3) 11에 위치 시킴 심판 위치 상태1 0 0 1 -> 가장 가까운 심판의 ..
-
1365 꼬인 전깃줄백준/이분탐색 2024. 7. 25. 22:30
이 문제는 가장 긴 증가하는 부분 수열 문제와 풀이법이 같다. 참고 :https://happy-fun.tistory.com/207 12015 가장 긴 증가하는 부분 수열 2import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = nhappy-fun.tistory.com 그래서 이 방법으로 문제를 풀면 된다. im..
-
1114 통나무 자르기백준/이분탐색 2024. 7. 23. 22:49
처음에는 우선순위 큐를 이용해서 풀어보려고 했다. 아래와 같은 예시가 있을 때,5 5 34 2 5 3 1 1) 우선순위 큐에 (나무 시작 위치, 나무 끝 위치, 나무 길이) 값을 넣는다.- 맨 처음 우선순위 큐 : (0,5,5) 2) 우선순위 큐를 나무 길이 내림차순 정렬한다. 3) 우선순위 큐에서 제일 첫번째 값을 꺼낸다. 4) 즉, 제일 길이가 긴 나무를 잘라나간다고 생각하면 된다.꺼낸 나무의 중간부분을 자른다. (중간을 잘라야 제일 긴 나무의 길이를 최대한 짧게 할 수 있다.)0,5 의 중간은 2또는 3인데,4 2 5 3 1 중2 또는 3이 있으므로우선 2로 자른다면, 우선순위 큐에,(0,2,2)(2,5,3) 을 넣어주면 된다.. 이런 식으로 풀어나가려고 했으나시간초과 while 문을 이용했고,..