백준/그리디 알고리즘
-
1744 수 묶기백준/그리디 알고리즘 2024. 7. 22. 21:50
입력값에서 음수랑, 양수를 따로 받는다. 예를 들어 -10 -5 -1 0 1 2 3 4 5 이런식으로 입력값이 있을 때1) 양수는 양수 리스트에 담고, 내림차순 정렬-> 5 4 3 2 1 2) 음수와 0은 음수리스트에 담고, 오름차순 정렬-10 -5 -1 0 그런 다음에 맨 처음에 있는 값부터 다음수와 묶으면 된다. 즉 양수의 경우 -> 5 4 3 2 15*4 + 3*2 + 1 = 20 + 6 + 1 = 27 이 최대의 값이 되고, 음수의 경우-10 -5 -1 0(-10) * (-5) + (-1)*0 = 50 + 0 = 50 이 최대의 값이 된다. 0을 음수 리스트에 넣은 이유는,음수가 홀수개 있을 경우 나머지 1개는 수를 묶을 수 없어서음수 그대로 남게 되는데, 0을 곱해서 0으로 만들면 음수를 ..
-
1781 컵라면백준/그리디 알고리즘 2024. 7. 5. 10:50
일단,먼저 다음과 같이 생각해보았다 (시간초과 남) 일단, 입력값을 컵라면 수 내림차순으로 정렬하는 것이다. 예제의 경우 71 61 73 23 12 42 56 1 1 71 62 52 43 26 13 1 => 그리고 visit 배열을 만들어서1) 만약에 그 시간에 방문한 적이 없다면, 방문표시하고2) 혹시나 방문한 적이 있다면 그보다 작은 시간에 방문한 적 없다면 방문표시하는 것이다. 예를 들어서 [1]1 7 에서 기한은 1이므로visit[1] = true 이다.그리고 count = 7이 된다. (컵라면 수 ) [2]그 다음 컵라면 수가 많은 1 6은 기한이 1이다.하지만 이미 visit[1] = true 이므로그냥 넘어간다. [3] 그 다음은 2 5 인데visit[2] = false 이므로visit[..
-
12904 A와 B백준/그리디 알고리즘 2022. 5. 2. 23:03
시간초과가 날 수 있으니 조심해야 한다. 1. 문제 풀이 1) 문자열 S에서 문자열 T로 바꾸기 문제에 주어진 조건, - 문자열 뒤에 A 추가 - 문자열 뒤집고 뒤에 B 추가 모두 고려해야 한다. 2) 문자열 T에서 문자열 S로 바꾸기 이 방법은 비교적 쉽다. 문제 예제를 생각해보자. B : 문자열 S ABBA : 문자열 T 먼저 S에서 T로 바꾼 후, T에서 S로 바꾸는 과정을 살펴보자. 가. S에서 T로 바꾸기 1. 문자열 뒤에 A를 추가한다. B => BA 2. 문자열을 뒤집고 뒤에 B를 추가한다. BA => ABB 3. 문자열 뒤에 A를 추가한다. ABB => ABBA 나. T에서 S로 바꾸기 위의 과정을 거꾸로 하면 된다. 1. 문자열 뒤에서 A 제거한다. ABBA => ABB 2. 문자열 뒤에..
-
2872 우리집엔 도서관이 있어백준/그리디 알고리즘 2022. 5. 2. 20:01
1. 문제 풀이법 35421 이때 책 번호 5,4,3,2,1 순서로 생각해보면 된다. 자세히 살펴보자. 책을 빼서 맨 위에 올려 놓을 떄마다 count 를 증가시켜 보자. 1) 5는 그냥 그 자리에 두면 된다. 2) 4는 5 뒤에 있기 때문에 책을 빼서 맨 위에 올려 놓아야 한다. => 43521 count = 1 3) 3은 4뒤에 있기 때문에 책을 빼서 맨 위에 올려 놓아야 한다. => 34521 count = 2 4) 2도 마찬가지이다. => 23451 count = 3 5) 1도 마찬가지이다. => 12345 count = 4 최종 답은 4가 된다. 그러면 생각해보자. 35421에서, 5뒤에 있는 4,2,1은 모두 그 자리에서 빼서 맨 위에 올려 놓았다. 5앞에 있던 3 역시 이동이 있었다. 2)에..
-
2839 설탕 배달백준/그리디 알고리즘 2022. 3. 10. 23:15
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int sum = 0; if(N%5==0) { sum +=N/5; System.out.println(sum); return; } int a= N; while(3 5a+3b (a,b는 0 이상) 1)..
-
2437 저울(자바)백준/그리디 알고리즘 2022. 2. 19. 19:12
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int N; static int number []; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); number= new int [N]..
-
1439 뒤집기백준/그리디 알고리즘 2022. 2. 10. 15:28
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; 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()); String ..