soo 문제집 그리디 easy 문제 중 68문제를 풀었고, 그중 힌트를 참고한 문제 및 정리하기 위해 해당 글을 작성합니다.
| 문제번호 | 제목 | 난이도 |
|---|---|---|
| 13170번 | 떨어진 수정 | 실버 4 |
| 15904번 | UCPC는 무엇의 약자일까? | 실버 5 |
| 12782번 | 비트 우정지수 | 실버 4 |
| 17262번 | 팬덤이 넘쳐흘러 | 실버 4 |
| 17521번 | Byte Coin | 실버 4 |
| 19939번 | 박 터뜨리기 | 실버 4 |
| 1758번 | 알바생 강호 | 실버 4 |
13170번 떨어진 수정
해결코드:
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());
double p = Double.parseDouble(st.nextToken());
int w = Integer.parseInt(st.nextToken());
bw.write((int)Math.ceil(p / w)+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 문해력이 해결 키포인트다.. 지문이 엄청 길고 쓸모없는 부분은 빠르게 스킵, 필요한 부분만 캐치하는 것이 이 문제의 해결 키포인트다
- 그리디하게 폭발 위험이 있는 힘 차이를 넘지 않는 최대 강도로 하면 최대 횟수를 구할 수 있다.
고민/풀이흐름:
- w씩 때려볼 때 안전하게 체크해볼 수 있으니까 p/w로 최대 w단위를 구한다
- 즉 망치의 최대 파워 중 폭발 위험이 있는 힘을 넘지 않도록만 때리면 된다
- 이때 양의 실수이기 때문에 double 형으로 지정해주었고, 횟수는 정수로 표현해야한다.
- p/w하고 나머지가 남았을 때, 그 나머지는 w보다 작을 것이고 그 만큼 한번만 망치를 더 때리면 되기 떄문에 롤림을 해야한다
- 따라서 Math.ceil을 통해 양의 실수를 올림하여 출력하였다.
링크:
15904번 UCPC는 무엇의 약자일까?
해결코드:
import java.io.*;
import java.util.*;
public class Main {
private static final char[] ucpc = {'U','C','P','C'};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] s = br.readLine().split(" ");
int pos = 0;
boolean isFind = false;
for (int i = 0; i < s.length; i++) {
for (int j = 0; j < s[i].length(); j++) {
if(s[i].charAt(j) == ucpc[pos]){
pos++;
}
if(pos > ucpc.length-1){
isFind = true;
break;
}
}
if(isFind){
break;
}
}
if(isFind){
bw.write("I love UCPC");
}else{
bw.write("I hate UCPC");
}
br.close();
bw.close();
}
}
해결 키포인트:
- UCPC를 미리 배열로 만들어두고 비교하며, 입력 문자열 길이를 고려했을 때 시간초과가 안 나기에 브루트포스로 풀 수 있다는 것이 해결 키포인트이다.
- 한가지 주의할 점이 contains는 사용할 수 없다. contains는 UCPC의 순서가 바뀌어도 포함된다고 하기 때문이다.
고민/풀이흐름:
- 미리 UCPC 글자를 char 배열로 관리해둔다
- 입력 문자를 split하여 배열에 있는 모든 문자열들과 각 단어들을 UCPC배열과 비교한다
- 만약 UCPC 배열의 단어중 하나와 같으면 pos를 증가시킨다
- 이후 pos가 UCPC 배열의 크기보다 크다면 UCPC로 축약할 수 있으므로 그에 맞는 문자열을 출력한다.
링크:
12782번 비트 우정지수
해결코드:
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 T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
String p1 = st.nextToken();
String p2 = st.nextToken();
int count0 = 0;
int count1 = 0;
for (int j = 0; j < p1.length(); j++) {
if(p1.charAt(j) == '0' && p2.charAt(j) == '1'){
count0++;
}else if(p1. charAt(j) == '1' && p2.charAt(j) == '0'){
count1++;
}
}
int ans = count0;
ans = Math.max(ans, count1);
bw.write(ans+"\n");
}
br.close();
bw.close();
}
}
해결 키포인트:
- 한쪽이 0이고 1인경우, 반대쪽이 1이고 0인경우를 각각 세어주는 것이 키포인트이다.
고민/풀이흐름:
- 한쪽이 0이고 1인경우, 반대쪽이 1이고 0인경우를 각각 세어준다
- 정답에 한쪽 값을 두고 더 큰 값을 정답으로 한다
링크:
17262번 팬덤이 넘쳐흘러
해결코드:
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 start = 0;
int end = 100001;
int n = Integer.parseInt(br.readLine());
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
if(s > start){
start = s;
}
if(e < end){
end = e;
}
}
int ans = start - end;
if(ans < 0){
bw.write("0");
}else{
bw.write(ans+"");
}
br.close();
bw.close();
}
}
해결 키포인트:
- 그리디하게 시작과 끝의 범위를 점점 줄여나가는게 문제 해결의 키포인트이다.
고민/풀이흐름:
- start와 end를 각각 최대 값으로 지정한다
- 이어서 팬의 시작과 끝 시간이 들어오면 start와 end를 비교하여 그 범위를 좁혀나간다
- ans에 start - end를 넣어주고 0보다 작으면 0, 아니면 ans를 출력한다.
링크:
17521번 Byte Coin
해결코드:
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());
long w = Long.parseLong(st.nextToken());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
long coin = 0;
int now = 0;
for (int i = 0; i < n - 1; i++) {
if(coin == 0 && arr[i] < arr[i+1]){
coin = w / arr[i];
w -= coin * arr[i];
}
if(arr[i] > arr[i+1]){
w += coin * arr[i];
coin = 0;
}
}
w += coin * arr[n-1];
bw.write(w+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 사는 시점과 파는 시점을 그리디하게 정해서 w의 값을 갱신해나가면된다
- 마지막날 다 파는 경우도 추가적으로 고려해야한다.
고민/풀이흐름:
- 각 일자별 코인 가격에 대해 배열로 상태를 관리한다
- coin이 0이고 다음날보다 작을 경우 매수한다.
- 다음날보다 현재가 더 큰 경우는 매도한다.
- 마지막날 코인을 모두 팔아주고 w를 출력한다.
링크:
19939번 박 터뜨리기
해결코드:
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());
int sum = 0;
for (int i = 0; i < k; i++) {
sum += (i+1);
}
if(n < sum){
bw.write("-1");
}else{
int ans = k-1;
n -= sum;
if(n%k != 0){
ans++;
}
bw.write(ans+"");
}
br.close();
bw.close();
}
}
해결 키포인트:
- 가장 그리디하게 최소로 담을 수 있는 경우는 순차적으로 1부터 담는 경우다
- 이때 만약 순차적으로 담은 그 숫자의 합이 n보다 크면 나눠담을 수 없는 것이다
- 아니라면 더 공을 나눠 담아야 할 수도 있으므로 일단 ans에 최소 차이인 k-1로 초기화한다
- n은 sum만큼 빼서 남은 공의 개수만 n에 남긴다
- 만약 n%k가 0이 아니면 ans를 증가시키고 ans를 출력한다.
고민/풀이흐름:
링크:
1758번 알바생 강호
해결코드:
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);
long first = 0;
for (int i = 0; i < n; i++) {
if(arr[i] - i > 0){
first += arr[i] - i;
}
}
Arrays.sort(arr, Collections.reverseOrder());
long second = 0;
for (int i=0; i<n; i++){
if(arr[i] - i > 0){
second += arr[i] - i;
}
}
long ans = Math.max(first, second);
bw.write(ans+"");
br.close();
bw.close();
}
}
해결 키포인트:
- 팁을 그리디하게 많이 받기 위해서는 낮게 팁을 주려는 사람의 금액도 끌어모으거나 높게 주는 사람들의 팁만 가져가는 경우를 비교해서 더 큰 값을 선택하는 것이 키포인트다.
고민/풀이흐름:
- 오름차순 정렬을 통해 낮게 팁을 주는 사람의 금액을 끌어모으는 경우의 값을 저장한다
- 높게 주는 사람들의 팁만을 가져가기 위해서 내림차순 정렬을 하고 그 금액의 값을 저장한다
- 두 값을 비교해서 더 큰 값을 ans에 넣고 출력한다
- 이때 입력값이 크기 int타입을 벗어나기 때문에 long타입으로 지정하였다.
링크:
Software Developer