[분류]
- greedy
[문제링크]
[요구사항]
- 코드의 인덴트를 올바르게 고치는 편집 회수의 최소값을 구한다.
[풀이]
- 우선 최종 목표와 현재 숫자의 차이인 diff배열을 생성한다.
- 이제 diff[0]부터 diff[n-1]까지 같은 그룹이라고 생각하고 diff[0]부터 하나씩 쳐낸다.
- diff[i-1]을 prev로 두고 diff[i]와 비교해서 다른 부호면 애초에 같이 tab을 더하거나 빼줄 수 없으므로 같은 그룹이 아니기 때문에 res에 diff[i-1] == prev를 더해주고 제외시킨다.
- 또는, prev와 diff[i] 모두 양수일 때는 오름차순, 모두 음수일 때는 내림차순이여야 뒤의 것들도 계속해서 쳐낼 수 있기 때문에 그렇게 되지 않으면 diff[i]-prev의 절댓값만큼 res에 더해준다. 이것은 diff[i]와 prev의 차이를 0으로 만든다는 의미로, 뒤의 계산 과정에서 커버할 수 있게 해주는 것이다.
- 둘 다 해당하지 않으면 그냥 prev를 diff[i]로 옮겨주는 식으로 계속 진행한다.
- 마지막에 하나남은 prev의 절댓값을 res에 더해주고 출력한다.
[코드]
//BOJ_2879_코딩은예쁘게
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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[] diff = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
diff[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
diff[i] = Integer.parseInt(st.nextToken()) - diff[i];
}
int prev = diff[0];
int res = 0;
for(int i=1;i<n;i++){
if(prev*diff[i]<0){//앞의 것과 지금 것이 부호가 다르면 같은 그룹 X -> 즉, 앞에꺼는 따로 처리
res+=Math.abs(prev);
prev = diff[i];
}
else if(prev*(prev-diff[i])>0){//양수일 때 오름차순, 음수일 때 내림차순으로 되지 않으면 역시 그룹X
// -> 앞에꺼가 지금꺼랑 같은 값 될 수 있을 때 까지만 움직이기(앞에 곱해준 prev는 단순히 부호용
res+=Math.abs(prev - diff[i]);
prev = diff[i];
}
else{//정상적이면 뒤에서 움직일 때 prev도 같이 커버되니까 넘어가기(같은그룹O)
prev = diff[i];
}
}
res+=Math.abs(prev);//맨 마지막에 남은거 하나 절댓값으로 더하기
System.out.println(res);
}
}
[통과여부]
[느낀점]
처음에는 dp로 풀려고 했지만 그룹지은 모든 숫자들을 전부 배열로 둔다는 것이 도저히 불가능하다고 판단했고, 도저히 뭘 속성으로 써야하는지 몰라서 포기했다. 이후에 greedy의 느낌으로 앞에서부터 하나씩 쳐낸다는 생각으로 구현을 해보자고 생각했다. greedy로 생각하는게 뭔가 확실성, 정당성이 있어야해서 어려운 것 같다.