[JAVA] 백준 14649 : 문홍안

백준 14649 : 문홍안

문제 설명

밟았을 때 B->R->G->B 규칙으로 색깔이 변하는 100개의 돌로 이루어진 징검다리를 N명의 비서가 돌의 번호(idx)에 위치하여 좌 혹은 우로 이동합니다.

최종적으로 총 재산 P를 B, R, G 색상의 갯수로 배분한 결과를 소수점 둘째 자리까지 출력합니다.

---

풀이 방법

• 핵심은 idx의 위치에서 밟기 시작하는 돌의 번호입니다.
  • idx에서 출발하는 비서는 L방향으로 이동하면 idx-1부터, R방향으로 이동하면 idx+1부터 밟아 색깔을 바꿀 수 있습니다.
  • 하지만 0번째 idx부터 1번째 칸으로 생각하므로, L방향으로 이동하면 Idx-2부터, R방향으로 이동하면 idx부터 밟아 색깔을 바꿉니다.
• 모듈러(%) 계산을 이용해 돌을 밟은 횟수를 B,R,G 세가지 경우로 축소합니다.
• printf의 출력문을 이용해 소수점 두번째 자리수를 출력합니다.

---

코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    //    p_14649 : 문홍안
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        double P = Double.parseDouble(br.readLine().trim());
        int N = Integer.parseInt(br.readLine().trim());
        int[] steps = new int[100];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken());
            char dir = st.nextToken().charAt(0);
            if (dir == 'R')
                for (int j = idx; j < 100; j++) steps[j]++;
            else  // 'L'
                for (int j = idx - 2; j >= 0; j--) steps[j]++;
        }

        int[] count = new int[3]; // blue : 0, red : 1, green : 2
        for (int c : steps) count[c % 3]++;

        double blue = P * count[0] / 100.0;
        double red = P * count[1] / 100.0;
        double green = P * count[2] / 100.0;
        System.out.printf("%.2f\n%.2f\n%.2f", blue, red, green);
    }
}

---

핵심 로직 설명

• 핵심은 idx의 위치에서 밟기 시작하는 돌의 번호입니다.
  • idx에서 출발하는 비서는 L방향으로 이동하면 idx-1부터, R방향으로 이동하면 idx+1부터 밟아 색깔을 바꿀 수 있습니다.
  • 하지만 0번째 idx부터 1번째 칸으로 생각하므로, L방향으로 이동하면 Idx-2부터, R방향으로 이동하면 idx부터 밟아 색깔을 바꿉니다.
• 모듈러(%) 계산을 이용해 돌을 밟은 횟수를 B,R,G 세가지 경우로 축소합니다.
• printf의 출력문을 이용해 소수점 두번째 자리수를 출력합니다.

---

시간복잡도

• 시간복잡도: O(N)

---

회고

• 인덱스를 평소에 신경써야함을 알려주는 문제였다.

---

참고

없음