"꾸준하고 완벽한 한 걸음"

greedy 34

[백준 23351] 물 주기 [Java]

문제23351번: 물 주기 23351번: 물 주기 boj.ma 풀이첫 캣닢이 죽는 날짜를 최대한 미루도록 물을 주는 문제다.이를 위해서는 남은 수분이 적은 캣닢에게 물을 주는 것이 최선이다.따라서 오름차순으로 정렬 후 K개의 캣닢에게 B-1만큼 물을 주고, 물을 주지않은 나머지 캣닢들은 1씩 감소시키면 된다. Arrays.sort(arr); while (isValid(arr)) { for (int i = 0; i 이후에는 다시 수분이 적은 순대로 정렬 후 날짜를 늘려주자. Arrays.sort(arr); ++day; }풀이 시간5분소스코드https://github.com/rogi-rogi/problem-sol..

[백준 14655] 욱제는 도박쟁이야!! [Java]

문제https://www.acmicpc.net/problem/14655 풀이주어진 규칙대로 동전을 뒤집어 게임에서 얻을 수 있는 최대 점수를 구하는 문제다. 규칙은 다음과 같다.항상 연속한 3개의 동전만 뒤집는다.동전 배열의 양 끝에서 벗어나서 양 끝의 동전만 뒤집거나양 끝의 두 개 동전만 뒤집는 것도 가능하다.동전을 뒤집는 횟수에 제한은 없다.여기서 중요한 사실은 동전을 뒤집는 횟수에 제한이 없다는 것이다.즉 어느 곳에 위치한 동전이든 결국 내가 원하는 대로 뒤집을 수 있다.따라서 주어진 2개의 동전 목록에 대해 절댓값을 더해주면 정답이 된다. // Solve int sum = 0; for (int i = 0; i 풀이 시간17분소스코드https://github.c..

[백준 01758] 알바생 강호 [Java]

문제https://www.acmicpc.net/problem/1758 풀이대기 순번 만큼 줄어든 팁을 최대한 많이 받기 위해 손님의 순서를 바꿔야 하는 문제다.팁 - 대기 순번이 0 이하인 경우에는 0원으로 계산하며, 대기 순번은 점점 커진다.따라서 작은 팁이 늦은 대기 순번으로 계산할 때 더 많은 팁을 받을 수 있다.입력받은 팁들을 내림차순으로 정렬해주자. // Solve Arrays.sort(A, Comparator.reverseOrder()); 팁 - 대기 순번의 계산 결과가 0이하가 될 때 까지 받을 수 있는 팁들을 계산하면 된다.N은 최대 10만이며 int의 범위를 초과한다 결과는 long으로 담아주자. long sum = 0; f..

[백준 32335] 부자가 될 거야! [Java]

문제https://www.acmicpc.net/problem/32335 풀이주어진 문자열 S의 각 자릿수를 회전시켜 가장 작은 수를 만드는 문제다.총 M번 회전 시켜야 하며 수는 증가하는 방향으로 회전해야 한다.맨 앞자리부터 시작해서 0으로 만들 수 있을 만큼 M이 크다면 돌려주고, 아니면 다음 수로 넘어가면 된다. // Solve for (int i = 0; i '0') { final int num = S[i] - '0'; if (num + M >= 10) { S[i] = '0'; M -= (10 - num); } ..

[백준 27370] 친구와 배달하기 [Java]

문제https://www.acmicpc.net/problem/27370 풀이$P_A$, $P_B$에서 N개의 목적지를 전부 방문했을 때, 이동거리 총합의 최솟값과 두 지점의 이동거리 차이의 최솟값을 구하는 문제다.우선 두 지점을 오름차순으로 교환해주고 if (Pa > Pb) { int temp = Pa; Pa = Pb; Pb = temp; }우선 이동거리 총합이 최소가 되야 하기 때문에 두 지점의 평균값을 기준으로 각 지점의 이동거리를 계산해준다. final int mid = (Pa + Pb) / 2; long A = 0, B = 0; ..

[백준 31067] 다오의 경주 대회 [Java]

문제https://www.acmicpc.net/problem/31067 풀이주어진 배열 A의 모든 요소가 서로 다른 오름차순 배열로 만들기 위한 최소 횟수를 구하는 문제다.오름차순을 만들기 위해 요소에 K만큼 더할 수 있다. // Solve int cnt = 0; for (int i = 0; i 만약 조건에 부합하는 배열을 만들 수 없다면 결과를 -1로 변경하고 탐색을 중단하자. } else { cnt = -1; break; } }소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-..

[백준 19564] 반복 [Java]

문제https://www.acmicpc.net/problem/19564 풀이어떤 키를 누르든 A ~ Z부터 한 번씩 주어지므로주어진 문자열 S를 만들기 위해서는 각 문자가 이전 문자보다 순서가 사전순으로 뒤에 위치할 때만 추가로 키를 눌러도 되지 않는다.만약 이전 문자와 동일한 문자, 또는 순서가 앞서는 문자가 나온다면 키를 한번 더 눌러서 A-Z를 얻어야 한다. // Solve int cnt = 1; for (int i = 1; i 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/practice/19564.java

[백준 01052] 물병 [Java]

문제https://www.acmicpc.net/problem/1052 풀이N개의 병을 2개씩 합쳐서 하나의 병으로 만드는 문제다.만약 K개의 병으로 만들 수 없다면 병을 한 개 더 추가해 다시 합칠 수 있다.2개의 병을 한 개의 병으로 합치기 때문에 N을 최대로 합칠 수 있는 병의 수는 N을 이진수로 했을 때 1의 개수와 동일하다.예제 1번은 다음과 같다.1 1 1 1 1 1 1 1 1 1 1 1 12 2 2 2 2 2 14 4 4 18 4 1$13=1101_{(2)}$으로 필요한 병의 수는 3개지만, K는 2이므로 병을 더 추가해야 한다.$14 = 1110_{(2)}$에 대해 K는 2, 추가된 병은 1개다. 14개의 병을 합쳐 총 3개의 병에 { 8, 4, 2 }담을 수 있다.이를 코드로 구현하면 다음..

[백준 17521] Byte Coin [Java]

문제https://www.acmicpc.net/problem/17521 풀이가격이 낮을 때 사고 높을 때 팔아서 마지막에 얻는 최종 현금의 최댓값을 계산하는 문제다.사고 파는 과정에서 최종 현금은 매우 커질 수 있다. long으로 계산해야 한다.항상 구매 또는 판매 가능한 최대 수량의 코인을 거래하는 것이 좋다.현금이 항상 나누어 떨어지지 않으니 나머지가 있음에 유의하자. // Solve long coin = 0; for (int i = 1; i A[i - 1]) { coin = W / A[i - 1]; W %= A[i - 1]; } else if (coin > 0 && A[i] 마지막에 코인..

[백준 10657] Cow Jog [Java]

문제https://www.acmicpc.net/problem/10657 풀이소의 위치가 증가하는 순서대로 소의 위치와 속도가 주어진다.소의 속도가 빠르다면 결국 자신보다 앞에 있는 소를 추월하게 되는데 이 때 같은 그룹이 된다.같은 그룹이 되면, 가장 느린 소의 속도에 맞춰 이동한다.따라서 가장 뒤에 있는 소를 기준으로 속도가 같거나 작다면, 새로운 그룹이 될 수 있다. int cnt = 1, curSpeed = speeds[N - 1]; for (int i = N - 2; i >= 0; --i) { if (speeds[i] 소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-j..