B068:チョコの分割 - 누적합

문제요약

칸의 총합이 같도록 초코를 분할해 가져라

---

난이도

B Rank

---

풀이 포인트

• 누적합
• new string('A', 3) = AAA

---

REVIEW

 

연속된 칸의 합을 구하는 건!! 누적합!!!

누적합 정말 쉬운 건데 자꾸 바로 떠오르지 않아서 매번 for문으로 합을 구해버린다.

 

그리고 같은 문자 n개 이어붙여 문자열 만들고 싶을 때, string 생성하는 법도 좀 알아두기.

간단한 걸 비효율적으로 풀고, 거기다 오답이면 좀 

---

CODE

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var line = Console.ReadLine().Split();
        int h = int.Parse(line[0]);
        int w = int.Parse(line[1]);

        int[,] choco = new int[h, w];

        for (int i = 0; i < h; i++)
        {
            var row = Console.ReadLine().Split();
            for (int j = 0; j < w; j++)
            {
                choco[i, j] = int.Parse(row[j]);
            }
        }

        List<string> result = new List<string>();

        for (int i = 0; i < h; i++)
        {
            int[] row = new int[w];
            for (int j = 0; j < w; j++)
            {
                row[j] = choco[i, j];
            }

            int[] prefixSum = new int[w + 1];
            for (int j = 0; j < w; j++)
            {
                prefixSum[j + 1] = prefixSum[j] + row[j];
            }

            bool found = false;
            for (int j = 0; j <= w; j++) 
            {
                int left = prefixSum[j];
                int right = prefixSum[w] - prefixSum[j];
                if (left == right)
                {
                    string s = new string('A', j) + new string('B', w - j);
                    result.Add(s);
                    found = true;
                    break;
                }
            }

            if (!found)
            {
                Console.WriteLine("No");
                return;
            }
        }

        Console.WriteLine("Yes");
        foreach (var lineStr in result)
        {
            Console.WriteLine(lineStr);
        }
    }
}