soo 문제집 그리디 easy 문제 중 68문제를 풀었고, 그중 힌트를 참고한 문제 및 정리하기 위해 해당 글을 작성합니다.
| 문제번호 | 제목 | 난이도 |
|---|---|---|
| 5545번 | 최고의 피자 | 실버 3 |
| 11508번 | 2+1 세일 | 실버 4 |
| 14247번 | 나무 자르기 | 실버 2 |
| 2138번 | 전구와 스위치 | 골드 4 |
| 2785번 | 체인 | 실버 1 |
| 20300번 | 서강근육맨 | 실버 3 |
| 1080번 | 행렬 | 실버 1 |
| 1105번 | 팔 | 실버 1 |
| 16112번 | 5차 전직 | 실버 2 |
| 20365번 | 블로그2 | 실버 3 |
5545번 최고의 피자:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int aPrice = Integer.parseInt(st.nextToken());
int bPrice = Integer.parseInt(st.nextToken());
int aCal = Integer.parseInt(br.readLine());
Integer[] bcals = new Integer[n];
for (int i = 0; i < n; i++) {
bcals[i] = Integer.parseInt(br.readLine());
}
int allCal = aCal;
int allPrice = aPrice;
int ans = allCal / allPrice;
Arrays.sort(bcals, Collections.reverseOrder());
for (int i = 0; i < n; i++) {
if(ans <= (allCal+bcals[i])/(allPrice+bPrice)){
allPrice += bPrice;
allCal += bcals[i];
ans = allCal / allPrice;
}
}
bw.write(ans + "");
br.close();
bw.close();
}
}
해결 키포인트:
- 내림차순 정렬로 큰 열량부터 확인하는 그리디 알고리즘을 선택하는 것이 키포인트다
- 한가지 더 있는데, 한가지 공식을 이용해야한다. 칼로리 / 가격은 1원당 열량이다
고민/풀이흐름:
- 도우에 대한 열량과 가격을 저장하고, ans에는 1원당 도우의 열량을 저장한다
- 이후 토핑 열량을 내림차순 정렬하고 순회한다
- 만약 ans보다 현재 칼로리에 토핑 칼로리릍 더한 값(allCal + bcals)에서
현재 가격에 토핑 칼로리를 더한 값(allPrice + bPrice)이 더 크거나 같으면 현재 토핑의 가격과 열량을 전체 칼로리와 가격에 더해준다 - 이어서 ans를 다시 3번 과정을 통해 갱신된 값으로 다시 초기화한다
- 이 과정을 통해 완성한 ans를 출력하면 정답이 된다.
링크:
11508번 2+1 세일:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Integer[] arr = new Integer[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr, Collections.reverseOrder());
int ans = 0;
for (int i = 0; i < n; i++) {
if(i%3 == 2){
continue;
}
ans += arr[i];
}
bw.write(ans+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 내림차순 정렬 후, 3번째 것만 지불하지 않는 그리디 알고리즘으로 해결하는 것이 키포인트다
고민/풀이흐름:
- 입력 배열을 내림차순 정렬한 후, i%3==2로 3번째 값은 건너뛰고 나머지는 ans에 더한다
- 이후 ans를 출력하면 정답이 된다.
링크:
14247번 나무 자르기
해결 코드:
import java.io.*;
import java.util.*;
class Tree{
int nowHeight;
int growth;
public Tree(int nowHeight, int growth){
this.nowHeight = nowHeight;
this.growth = growth;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Tree[] tree = new Tree[n];
int[] tmp1 = new int[n];
int[] tmp2 = new int[n];
for (int i = 0; i < n; i++) {
tmp1[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
tmp2[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < n; i++) {
tree[i] = new Tree(tmp1[i], tmp2[i]);
}
Arrays.sort(tree, Comparator.comparingInt(o -> o.growth));
long ans = 0;
for (int i = 0; i < n; i++) {
ans += tree[i].nowHeight + ((long) i * tree[i].growth);
}
bw.write(ans+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 성장속도가 작은 나무부터 자르는 그리디 알고리즘이 해결 키포인트이다.
고민/풀이흐름:
- 현재 높이와 성장속도를 배열로 받고 tree 클래스를 만들어서 하나의 배열로 관리하낟
- 성장속도를 기준으로 오름차순 정렬하고, 현재 높이에 성장속도 * i(자르는 일자-1)을 더한 값을 ans에 더해준다
- 완성한 ans를 출력하면 정답이 된다.
링크:
2138번 전구와 스위치:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String[] input = br.readLine().split("");
int[] before1 = new int[n];
int[] before2 = new int[n];
int[] after = new int[n];
for (int i = 0; i < n; i++) {
int tmp = Integer.parseInt(input[i]);
before1[i] = tmp;
before2[i] = tmp;
}
input = br.readLine().split("");
for (int i = 0; i < n; i++) {
after[i] = Integer.parseInt(input[i]);
}
int count1 = 1;
int count2 = 0;
before1[0] = 1-before1[0];
before1[1] = 1-before1[1];
for (int i = 0; i < n-1; i++) {
if(before1[i] != after[i]) {
count1++;
before1[i] = 1 - before1[i];
before1[i + 1] = 1 - before1[i + 1];
if (i != n - 2) {
before1[i + 2] = 1 - before1[i + 2];
}
}
}
if(before1[n-1] != after[n-1]){
count1 = -1;
}
for (int i = 0; i < n-1; i++) {
if(before2[i] != after[i]) {
count2++;
before2[i] = 1 - before2[i];
before2[i + 1] = 1 - before2[i + 1];
if (i != n - 2) {
before2[i + 2] = 1 - before2[i + 2];
}
}
}
if(before2[n-1] != after[n-1]){
count2 = -1;
}
if(count1 == -1){
bw.write(count2+"");
}else if(count2 == -1){
bw.write(count1+"");
}else{
bw.write(Math.min(count1, count2)+"");
}
br.close();
bw.close();
}
}
해결 키포인트:
- 스위치 누를지 말지 선택하여, 그리디하게 해결해야 한다
- 이때 첫번째 전구를 반전 시켜야되는지 여부에 따라 구분하고 각자 확인하여 해결하는 것이 키포인트다.
- boolean배열이 아니고 Integer에서 반전을 원할 경우 1-before1 형식으로 하면 된다
고민/풀이흐름:
- 처음을 반전시켜야되는지 구분하기 위해 두개의 before 변수를 만들었다
- count1에는 반전해야하는 경우, count2에는 반전하지 말아야하는 경우다
- 0부터 n-1까지 각각 순회하면서 만약 현재가 after와 같지 않으면 n-2가 아닌 경우, 현재와 현재의 다음 그리고 그 다음까지 반전시켜준다
- 만약 현재가 n-2라면 현재와 현재의 다음까지만 반전시킨다
- 각각 순회 후 n-1이 after와 같은지 확인하고 다르면 불가능한 경우이므로 -1로 초기화한다
- 이제 각각 -1인 경우 반대의 count를 출력하고 둘다 -1이 아닌 경우 둘 중 더 작은 값을 출력한다
링크:
2785번 체인:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
List<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(Integer.parseInt(st.nextToken()));
}
Collections.sort(arr);
int count = 0;
while(true){
if(arr.size() <= 1){
break;
}
arr.set(0, arr.get(0)-1);
arr.remove(arr.size() - 1);
if(arr.get(0) == 0){
arr.remove(0);
}
count++;
}
bw.write(count+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 오름차순 정렬 후, 앞에 있는 체인의 길이만큼 뒤에 있는 체인을 하나씩 제거해가며 그 수를 세어나가는 것이 해결 키포인트이다
- 이때 List의 list.set과 list.remove를 적극 활용하였다
- list.set(0, arr.get(0)-1)은 0번 위치의 값을 0번 위치의 값 -1로 바꾸는 기능이다
- list.remove(arr.size()-1)은 해당 인덱스 위치의 값을 제거하는 기능이다.
고민/풀이흐름:
- 그리디하게 풀기 위해 체인의 길이를 오름차순 정렬 한 뒤, 맨앞 체인을 하나씩 떼어서 맨 뒤에 있는 체인과 하나씩 연결하는 것이 최소한의 고리 수라고 판단하였다
- 따라서 오름차순 정렬한 뒤, 순회를 통해 해결하는데 만약 크기가 1보다 작거나 같으면 탈출하도록 하였다
- 맨 처음에 있는 체인의 길이를 1씩 줄이면서 맨 뒤의 값을 하나씩 제거한다
- 만약 맨 처음에 있는 체인의 길이가 0이 된다면 첫번째 값을 제거한다. 이러면 뒤에 있는 값이 앞땡겨져 온다
- 순회마다 count++를 통해 개수를 세어준다
- 완성한 결과인 count를 출력하면 정답이 된다.
링크:
20300번 서강근육맨:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = Long.parseLong(st.nextToken());
}
Arrays.sort(arr);
long ans = 0;
if(n % 2 == 1){
ans = arr[n-1];
for (int i = 0; i < (n-1) / 2; i++) {
ans = Math.max(ans, arr[i] + arr[n-2-i]);
}
}else{
for (int i = 0; i < n/2; i++) {
ans = Math.max(ans, arr[i] + arr[n-1-i]);
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 그리디하게 풀기 위해 오름차순 정렬을 하고, 홀수와 짝수로 나눠서 앞과 뒤를 더해나가면서 최대값을 구하는 것이 해결 키포인트다.
고민/풀이흐름:
- 먼저 오름차순 정렬을 해주고 홀수와 짝수로 구분한다
- 이때 순회는 절반만 하는데 홀수일 때는 (n-1) / 2, 짝수일 때는 n/2만큼 순회한다
- 홀수일때는 먼저 맨 뒷값을 ans에 넣고 순회하면서 앞과 뒤인 i, n-2-i를 더한 값을 비교하여 더 큰 값을 ans에 넣는다
- 짝수일 때는 앞과 뒤인 i, n-1-i를 더한 값과 ans를 비교하여 더 큰값을 넣어준다
- 이렇게 완성한 ans를 출력하면 정답이 된다
링크:
1080번 행렬:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] arr1 = new int[n][m];
int[][] arr2 = new int[n][m];
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < m; j++) {
arr1[i][j] = Integer.parseInt(input[j]);
}
}
for (int i = 0; i < n; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < m; j++) {
arr2[i][j] = Integer.parseInt(input[j]);
}
}
boolean isOk = true;
int count = 0;
for (int i = 0; i < n-2; i++) {
for (int j = 0; j < m-2; j++) {
if(arr1[i][j] != arr2[i][j]){
count++;
for (int k = i; k < i+3; k++) {
for (int l = j; l < j+3; l++) {
if(arr1[k][l] == 1){
arr1[k][l] = 0;
}else{
arr1[k][l] = 1;
}
}
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(arr1[i][j] != arr2[i][j]){
isOk = false;
}
}
}
if(!isOk){
bw.write("-1");
}else{
bw.write(count+"");
}
br.close();
bw.close();
}
}
해결 키포인트:
- 배열을 순회하여 비교하면서 다른지점이 있으면 그 지점을 시작으로 3*3만큼 반전을 해주면 된다
고민/풀이흐름:
- 다른 지점이 발견되면 그때부터만 3x3만큼 추가로 순회한다.
- 이때 n-2, m-2만큼만 순회하면 되며, 만약 반전을 해야하는 경우에는 그 수를 세어준다
- 이후 다시 순회하여 다른 지점이 발견되면 -1을 출력하도록 하고 아니면 count를 출력하도록 한다
링크:
1105번 팔:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
String l = st.nextToken();
String r = st.nextToken();
int ans = 0;
if(l.length() == r.length()){
for (int i = 0; i < l.length(); i++) {
if(l.charAt(i) != r.charAt(i)){
break;
}
if(l.charAt(i) == '8'){
ans++;
}
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
해결 키포인트:
- L과 R이 같을때만 답이 존재한다는 것이 키포인트다
고민/풀이흐름:
- 몇가지 경우를 생각해보니 L과 R이 같을때만 답이 존재한다는 것을 알게 되었다
- 따라서 문자열로 받고 길이가 같을 때, 한쪽의 길이만큼 순회하고, 만약 두 문자가 같지않다면 탈출하며, 8을 발견할때마다 개수를 세어준다
- ans를 출력하면 정답이 된다.
링크:
16112번 5차 전직:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
long ans = 0;
int stone = 1;
for (int i = 1; i < n; i++) {
if(stone < k){
ans += (long) arr[i] * stone;
stone++;
}else{
ans += (long) arr[i] * stone;
}
}
bw.write(ans+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 오름차순 정렬해서 보상 경험치가 적은 퀘스트부터 더하는 것이 해결 키포인트다
- 적은 퀘스트부터 더해야지 손실이 가장 적게 난다.
고민/풀이흐름:
- 먼저 무조건 stone은 한개 가지고 있으니 1로 시작한다
- 오름차순 정렬 후, 두번째 값부터 탐색을 시작하는데, k개보다 적으면 돌의 개수만큼 현재 경험치를 더한다
- 만약 k개보다 크다면 그냥 곱해서 더해준다. 이때 long타입으로 지정해줘야 오버플로우가 발생하지 않는다.
- 완성한 ans를 출력하면 정답이 된다.
링크:
20365번 블로그2:
해결 코드:
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String s = br.readLine();
int blue = 0;
int red = 0;
char last;
if(s.charAt(0) == 'B'){
blue++;
last = 'B';
}else{
red++;
last = 'R';
}
for (int i = 1; i < n; i++) {
if(s.charAt(i) == 'R' && last == 'B'){
red++;
last = 'R';
}else if(s.charAt(i) == 'B' && last == 'R'){
blue++;
last = 'B';
}
}
int count = Math.min(red, blue);
bw.write(count+1+"");
br.close();
bw.close();
}
}
해결 키포인트:
- red로 다 칠하고 blue로 바꾸는 경우와, 반대인 경우 중 더 작은 경우 + 1을 선택하는 것이 해결 키포인트다
고민/풀이흐름:
- 목표하는 색 중 처음이 무슨 색인지 보고 개수를 세어준 뒤, 그 색을 변수에 초기화한다
- 두번째 값부터 확인하는데 만약 목표로 하는 색인데 변수의 색과 다르면 목표로 하는 색의 개수를 늘려주고 변수도 목표로 하는 색으로 바꿔준다
- 이후 더 작은 값을 고른 뒤, 그 값에 1을 더한다
- 지금까지 세어준 개수는 처음에 한 색으로 다 칠하고, 바꿔야할 색의 개수를 고른 것이기 때문에 처음에 한 색으로 다 칠해버리는 경우도 세어줘야하기 때문이다.
링크:
Software Developer