boj, 백준) 1802. 종이 접기(C#)

1. 문제 링크

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

1802번: 종이 접기

 

2. 문제 개요

종이를 접는데 두 가지 방법으로 접을 수 있다.

1. 오른쪽 반을 반시계 방향으로 접어서 왼쪽 반의 위로 접는다.

2. 오른쪽 반을 시계 방향으로 접어서 왼쪽 반의 아래로 접는다.

 

이때, 접혀져 있는 종이가 주어질 때, 실제로 접을 수 있는 방법인지 알아내는 프로그램을 작성하시오

 

3. 문제 힌트 & 풀이

실제로 종이를 접어보며 테스트해보자

토마토, 기러기 처럼 중심을 기준으로 대칭이 되어야 하나, 중심으로부터 같은 거리에 떨어진 숫자가 서로 다른 숫자여야 한다.

 

종이를 반 접은 상태(2겹)에서 

한 번 더 접는다는 것은 각 겹에 대해서 똑같은 행동을 하는 것과 같다(분할 정복).

 

그러므로 중심을 기준으로 왼쪽 오른쪽이 모두 팰린드롬(서로 다른)이 되어야 하고, 또 그 중심을 기준으로 팰린드롬(서로 다른).. 반복되어야 함.

 

 

※ 문제도 간단하고 C#이라 아무도 안 볼 것 같지만.. 그냥 기록으로 남겨봅니다..

 

 

4. 코드

using System;
using System.Collections.Generic;

namespace PScs
{
    class Solution
    {
        public static bool solution(ref string s, int l, int r)
        {
            if (r <= l)
                return true; 

            if (isPalindrome(ref s, l, r))
            {
                int mid = (l + r) / 2;
                return solution(ref s, l, mid - 1) && solution(ref s, mid + 1, r);
            }
            else
                return false;
        }
        public static bool isPalindrome(ref string s, int l, int r)
        {
            if (r <= l)
                return true;

            if (s[l] != s[r])
                return isPalindrome(ref s, l + 1, r - 1);
            else
                return false;
        }

        static void Main(string[] args)
        {
            int n = Int32.Parse(Console.ReadLine());
            
            while(Convert.ToBoolean(n--))
            {
                string s = Console.ReadLine();

                if (solution(ref s, 0, s.Length - 1))
                    Console.WriteLine("YES");
                else
                    Console.WriteLine("NO");
            }
        }
    }
}

 

5. 결과