문제
https://school.programmers.co.kr/learn/courses/30/lessons/148653?language=java
코드
class Solution {
public int cal(int[] arr, int i){
if(arr[i]==10){
arr[i-1]+=1;
arr[i]=0;
}
// 현재 값이 4이하이면 그대로 return
if(arr[i]<=4){
return arr[i];
}
// 현재 값이 5이면 앞자리 수 비교하고 return
else if(arr[i]==5){
if(arr[i-1]>=5){
arr[i-1]+=1;
return 10-arr[i];
}
else{
return arr[i];
}
}
// 현재 값이 6이상이면 10-현재 값 return
else{
arr[i-1]+=1;
return 10-arr[i];
}
}
public int solution(int storey) {
int answer = 0;
String temp=Integer.toString(storey);
int[] arr=new int[temp.length()+1];
// storey 숫자를 배열에 넣어줌
// 2554 -> {0, 2, 5, 5, 4}
for(int i=0; i<temp.length(); i++){
arr[i+1]=(int)temp.charAt(i)-'0';
}
// 일의 자리부터 넣어주며 동작 계산
for(int i=arr.length-1; i>=0; i--){
answer+=cal(arr, i);
}
return answer;
}
}
import java.util.*;
class Solution {
int N, answer;
public int solution(int storey) {
String storey_s = Integer.toString(storey);
N = storey_s.length();
int[] storeys= new int[N+1];
for(int i=1; i<=N; i++) {
storeys[i] = storey_s.charAt(i-1)-'0';
}
answer = Integer.MAX_VALUE;
process(N, storeys, 0);
return answer;
}
void process(int idx, int[] storeys, int total) {
if(idx == 0) {
answer = Math.min(answer, total + storeys[0]);
return;
}
//위로 올리기
storeys[idx-1]++;
process(idx-1, storeys, total + 10-storeys[idx]);
storeys[idx-1]--;
//아래로 내리기
process(idx-1, storeys, total+storeys[idx]);
}
}
어려웠던 부분
케이스를 나누는 작업이 어려웠다.
'문제풀이 > 그리디' 카테고리의 다른 글
[JAVA] [그리디] Pro 디펜스 게임 (0) | 2023.07.12 |
---|---|
[JAVA] [그리디] 백준 1339 단어수학 (0) | 2023.06.19 |
[파이썬] [그리디] 백준 1715 카드 정렬하기 (0) | 2023.04.10 |
[파이썬] [그리디] 백준 17615 볼 모으기 (0) | 2023.03.02 |
[파이썬] [그리디] 백준 2138 전구와 스위치 (0) | 2023.02.10 |