[Platinum I] 간단한 문제 - 15948

문제 링크

성능 요약

메모리: 14212 KB, 시간: 104 ms

분류

애드 혹, 해 구성하기, 수학

제출 일자

2025년 2월 10일 03:36:23

문제 설명

자연수
$n$, $m$과 자연수 수열 $A_1, A_2, \cdots, A_m$이 주어졌을 때, 다음 등식을 만족하는 자연수 수열 $B_1, B_2, \cdots, B_m$을 구하라.

입력

첫 번째 줄에 자연수 $n$과 $m$이 공백으로 구분되어 주어진다. ($1 \le n \le 10^{15}, 1 \le m \le 50$)
두 번째 줄에 수열 $A_1, A_2, \cdots, A_m$을 나타내는 정수 $m$개가 공백으로 구분되어 주어진다. ($1 \le A_i \le 1,000$)

출력

첫 번째 줄에 등식을 만족하는 수열 $B_1, B_2, \cdots, B_m$을 공백으로 구분하여 출력한다. 각 $B_i$는
$1$ 이상 $3\times10^{18}$ 이하여야 한다. 등식을 만족하는 수열이 여러 가지라면 그 중 아무거나 출력해도 된다. 만약 등식을 만족하는 수열이 존재하지 않는다면 첫 번째 줄에 $-1$을 출력한다.

문제 풀이

1. 왜 N이 홀수/짝수일 때 다르게 처리해야 하는가?

• 등식의 왼쪽에 있는 (2^m - 1)/n 항을 정수로 만들어야 하기 때문

• N이 홀수일 때는 현재 값을 바로 계산하고 N+1을 해서 짝수로 만든 후 2로 나눔

• N이 짝수일 때는 바로 2로 나눠서 더 작은 문제로 만듦

2. 왜 idx+M-1 위치에 값을 저장하는가?

• 짝수일 때 나중에 계산되는 값이 더 커져야 하기 때문
• 현재 남은 구간의 마지막 위치(idx+M-1)에 더 큰 값을 저장

3. 왜 (N + (1L << M) - 2) * A[idx + M - 1] 이런 계산을 하는가?

• 등식의 양변을 같게 만들기 위해 필요한 값을 계산해야 하기 때문
• 2의 M승을 사용하여 적절한 크기의 값을 만듦

4. 왜 M이 1일 때 따로 처리하는가?

• 마지막 하나 남은 값은 이전에 계산된 모든 값들과의 관계를 고려해야 하기 때문
• N*A[idx]로 간단히 계산하여 등식을 만족시킴

5. 왜 originalM을 따로 저장해야 하는가?

• M 값이 계속 감소하지만 최종 출력할 때는 원래 배열 크기가 필요하기 때문
• 처음 M 값을 originalM에 저장하여 출력에 사용

코드

코드 1

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static long N;
    static int M, originalM;
    static long[] A, B;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_15948_간단한문제/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Long.parseLong(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        originalM = M;
        A = new long[M];
        B = new long[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        // B 배열 계산
        int idx = 0;  // B배열의 현재 위치
        while(M > 0) {
            if(M == 1) {
                // 마지막 원소 처리
                B[idx] = N * A[idx];
                break;
            }
            
            if(N % 2 == 1) {  // N 홀수
                B[idx] = N * A[idx];
                N = (N + 1) / 2;
                idx++;
            } else {  // N 짝수
                // 마지막 원소는 따로 계산
                B[idx + M - 1] = (N + (1L << M) - 2) * A[idx + M - 1];
                N /= 2;
            }
            M--;
        }
        
        // 원래 길이(originalM)
        for(int i = 0; i < originalM; i++) {
            sb.append(B[i]);
            if(i < originalM-1) sb.append(" ");
        }
        sb.append('\n');

        System.out.println(sb);
        bw.flush();
        bw.close();
        br.close();
    }
}

---

코드 2 (재귀)

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static long N;
    static int M;
    static long[] A, B;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_15948_간단한문제/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Long.parseLong(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        A = new long[M];
        B = new long[M];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        solve(N, M, 0);

        for(int i=0; i<M; i++) {
            sb.append(String.valueOf(B[i]));
            if(i < M-1) sb.append(" ");
        }
        sb.append('\n');
        System.out.println(sb);
        bw.flush();
        bw.close();
        br.close();
    }

    private static void solve(long n, int m, int k){
        if(m == 1){
            B[k] = n * A[k];
            return;
        }

        if(n%2 == 1){
            B[k] = n * A[k];
            solve((n+1)/2, m-1, k+1);
            return;
        }
        else{
            solve(n/2, m-1, k);
            B[k+m-1] = (n + (1L<<m) - 2) * A[k+m-1];
        }
    }
}