문제
해결 방안 고민
•
사탕의 개수를 짝수개로 맞추고, 모든 학생의 사탕 개수를 같게 하고, 옆에 있는 학생에게 사탕 반개씩 주는 것이 문제의 요구사항이다.
•
문제는 이해했으나 조건을 어떻게 구현해야 할지 좀처럼 감이 잡히지 않았다.
해결 방법
•
각각의 조건들을 함수로 만들어서 진행해야 한다.
•
newCandies[(i + 1) % length] = candies[i] / 2 + candies[(i + 1) % length] / 2;
◦
이 부분이 문제풀이의 핵심이다. 배열의 인덱스와 나머지 연산을 활용하면 조건에 맞게 순환에 대한 계산을 진행할 수 있다.
코드
package algo250611;
import java.io.*;
import java.util.*;
// 백준 - The candy war(실버 5)
public class Baek9037 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 테스트 케이스
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(br.readLine());
int[] C = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
C[j] = Integer.parseInt(st.nextToken());
}
int count = 0;
while (true) {
C = checkCandy(C); // 사탕 짝수개 맞춘다.
if (isSameCandy(C)) {
break;
}
C = roundCandy(C);
count++;
}
System.out.println(count);
}
}
// 사탕 짝수개로 맞추기
private static int[] checkCandy(int[] candies) {
for (int i = 0; i < candies.length; i++) {
if (candies[i] % 2 == 1) {
candies[i]++;
}
}
return candies;
}
// 모든 학생의 사탕 개수 같게 하기
private static boolean isSameCandy(int[] candies) {
for (int candy : candies) {
// 모든 사탕은 같아야 하므로
if (candy != candies[0]) {
return false;
}
}
return true;
}
// 사탕 순환
private static int[] roundCandy(int[] candies) {
int length = candies.length;
int[] newCandies = new int[length];
for (int i = 0; i < length; i++) {
// 맨끝에 있는 학생은 맨 처음 학생으로 줘야 하기에 뒤에 길이만큼 나눈 나머지로 처리
newCandies[(i + 1) % length] = candies[i] / 2 + candies[(i + 1) % length] / 2;
}
return newCandies;
}
}
Java
복사
느낀 점
요즘 들어 알고리즘 공부가 더 어려워지는 느낌이 든다. 처음에는 쉬운 문제부터 접근하다 보니 그리 오랜 시간이 흐르지 않았지만 점점 해결하는 데 있어 시간이 길어진다. 답답함을 느낄 때가 많고 도저히 이해가 되지 않는 경우 해설집이나 다른 블로그를 참고하여 문제에 대한 접근법을 익히고자 노력한다. 알고리즘 공부는 아무리 해도 쉽게 늘지를 않으니 계속 이렇게 하는 게 맞나 싶기도 하지만 그렇다고 중간에 포기하면 이제까지 공부한 게 다 물거품이 될 것이다. 어차피 시작한 거 끝을 봐야 하지 않겠는가.