[BAEKJOON] 백준 31846: 문자열 접기 (C#)

문제 링크

https://www.acmicpc.net/problem/31846

 

 

문제

기다란 종이에 알파벳 대문자로만 이루어진 문자열이 한 줄로 쓰여 있다. 예를 들어 아래 그림과 같이 종이에 “ABAACA”가 쓰여 있다고 가정하자.

 

이제 이 종이를 한 번만 접을 것이다. 종이는 서로 이웃한 문자 사이에서만 접을 수 있다. 예를 들어 아래 그림과 같이 위 종이를 4번째 문자와 5번째 문자 사이에서 접을 수 있다.

이때 서로 맞닿은 문자 쌍 중에서, 서로 같은 문자가 맞닿은 쌍의 개수가 이 접기의 점수가 된다. 예를 들어 앞에서의 접기의 점수는 1점이 된다. 하지만 아래 그림과 같이 3번째 문자와 4번째 문자 사이에서 종이를 접으면 점수는 2점이 된다.

이제 여러분은 알파벳 대문자로만 이루어진 문자열 S가 주어질 때, 다음과 같은 질문 Q개에 답해야 한다.

•  l r: 문자열 S의 l번째 문자, (l+1)번째 문자, ⋯, r번째 문자가 차례대로 종이에 쓰여 있을 때, 종이를 한 번 접어서 얻을 수 있는 최대의 점수는 몇 점인가?

 

 

입력

첫 번째 줄에 문자열의 길이를 나타내는 정수 N이 주어진다.

두 번째 줄에 알파벳 대문자로만 이루어진 문자열 S가 주어진다.

세 번째 줄에 정수 Q가 주어진다.

네 번째 줄부터 Q개 줄에 걸쳐 위에서 설명한 질문을 나타내는 정수 l, r이 공백으로 구분되어 주어진다.

 

출력

각 질문의 답을 나타내는 정수를 순서대로 한 줄에 하나씩 출력한다.

 

 

제한

•  2≤N≤50
•  1≤Q≤100
•  1≤l<r≤N 

 

 

 

통과한 답안

namespace _31846
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            int Q = int.Parse(Console.ReadLine());

            List<Tuple<int, int>> queries = new List<Tuple<int, int>>();
            for (int test = 0; test < Q; test++)
            {
                string[] inputs = Console.ReadLine().Split(' ');
                int l = int.Parse(inputs[0]);
                int r = int.Parse(inputs[1]);
                queries.Add(new Tuple<int, int>(l, r));
            }

            foreach (var query in queries)
            {
                int l = query.Item1 - 1;
                int r = query.Item2 - 1;
                int maxScore = 0;

                for (int mid = l; mid < r; mid++)
                {
                    int score = 0;
                    int left = mid;
                    int right = mid + 1;

                    while (left >= l && right <= r)
                    {
                        if (S[left] == S[right])
                        {
                            score++;
                        }
                        left--;
                        right++;
                    }

                    if (score > maxScore)
                    {
                        maxScore = score;
                    }
                }

                Console.WriteLine(maxScore);
            }
        }
    }
}

 

길이가 N인 문자열 S가 주어졌을 경우에,

해당 문자열의 l부터 r까지의 문자들을 가지고 특정 위치에서 반을 접었을 경우에

맞닿은 문자가 같은 경우에 1점씩 추가하는 방식으로 점수를 계산했을 때,

최대 점수를 찾는 과정을 Q번 하는 문제이다.

 

문제를 풀이하는 과정에서는 주어진 입력값들을 처리한 후에

l과 r에 대해서 각각의 부분 문자열에서 최대 점수가 되는 경우를 찾도록 구현하였다.

 

여기서 주어진 l과 r은 문자의 위치를 나타내므로 1씩 빼준 뒤에,

for 문을 이용하여 모든 위치에서 반을 접도록 하였으며,

각각의 반을 접은 위치에 대해서 while문을 이용하여 점수를 계산하였다.

만약 점수가 현재 최대 점수보다 높다면 최대 점수를 갱신하도록 하였다.

 

문제를 처음 보고 어떤 방식을 이용해서 간략하게 풀이할 수 있을지 고민했지만,

이 문제의 경우에는 모든 경우에 대해서 점수를 계산하는 것이 효율적이라 판단하여

각각의 경우에 직접 점수를 계산하도록 구현하였다.