👨‍💻 문제

층마다 다른 수의 칸이 존재,
1과 9를 배치하여 상단 층의 합이 하단 층의 합보다 낮도록 해를 구성하는 문제

---

✍️ 풀이

최대 층의 수와 최대 칸의 수가 100000으로 크기 때문에 실제로 값을 채우지 않고,
각 층의 칸 수와 각 층의 합과 층마다 사용된 9의 수만을 저장할 것이다.

기본값은 모두 1로 두며, 필요 시 9로 대체한다.

1 1 1 1				// 4, 4, 0
1 1					// 2, 2, 0
1 1 1 1 1 1 1		// 7, 7, 0
1 1 1 1 1 1			// 6, 6, 0

⬇ 9 최소 소비

우선 상단 층의 합이 하단 층의 합보다 낮도록 한다.
상단에서부터 하단으로 내려가며 하단이 최소한 상단보다 크도록 값을 9로 바꾼다.

1 1 1 1
9 1
9 1 1 1 1 1 1
9 9 1 1 1 1

⬆ 남은 9 모두 소비

위 과정에서 남은 9를 모두 소비하여야 한다.
이번에는 하단에서부터 상단으로 거슬러 올라가며 소비할 수 있을만큼 소비한다.

1 1 1 1
9 1
9 9 1 1 1 1 1
9 9 9 9 9 9

---

📄 전체 소스코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        int[] numCnt = new int[N];
        int[] sum = new int[N];
        for (int i=0; i<N; i++) {
            numCnt[i] = sum[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int one = Integer.parseInt(st.nextToken());
        int nine = Integer.parseInt(st.nextToken());

        int[] nineCnt = new int[N];
        // 9를 필요한 만큼만 소비
        // 위에서부터 최대한 적게
        for (int i=1; i<N; i++) {
            while (sum[i-1] >= sum[i]) {    // can be faster
                sum[i] += 8;
                nineCnt[i]++;
                nine--;
                if (nineCnt[i] > numCnt[i] || nine < 0) {
                    System.out.println(-1);
                    return;
                }
            }
        }

        // 남은 9를 소비
        // 아래부터 최대한 많이
        for (int i=N-1; i>=0; i--) {
            if (nine == 0) {
                break;
            }
            while (nineCnt[i] < numCnt[i] && nine > 0 && (i==N-1 || sum[i+1] > sum[i] + 8)) {
                nineCnt[i]++;
                sum[i] += 8;
                nine--;
            }
        }

        if (nine > 0) {
            System.out.println(-1);
            return;
        }

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<N; i++) {
            int n = nineCnt[i];
            int o = numCnt[i] - nineCnt[i];
            for (int j=0; j<numCnt[i]; j++) {
                sb.append(j < n ? 9 : 1);
                sb.append(j == numCnt[i]-1 ? '\n' : ' ');
            }
        }
        System.out.print(sb);

    }

}