용용코딩

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

• 문제

• 문제풀이

분할정복(divide and conquer) 알고리즘을 사용하여, NxN 크기의 배열에서 모든색이 같은 색종이의 개수를 찾는 문제를 해결해야한다. 

이 문제는 큰 배열을 작은 크기의 4개의 배열로 나눈 뒤, 각각의 배열에서 두 번째로 작은 값을 찾는 과정을 반복하여 해결합니다. 따라서, 재귀함수를 사용하여 문제를 풀어나간다.

• 코드 1

using System.Collections.Immutable;
using System.Text;
using System.Xml;

namespace ConsoleApp24
{
    internal class Program
    {
        public static int[,] arr;
        public static int white=0;
        public static int blue=0;
        public static void Check(int size, int x, int y)
        {
            int color = 2;
            bool check = true;
            if(arr[x, y] == 1)
            {
                color = 1;
            }
            else
            {
                color = 0;
            }

            for(int a = x; a < x + size; a++)
            {
                for(int b = y; b < y + size; b++)
                {
                    if (arr[a, b] != color)
                    {
                        check = false;
                        break;
                        

                        
                    }
                }
                if (!check) break;
            }
            if (check)
            {
                if (color == 1)
                {
                    blue++;
                }
                else
                {
                    white++;
                }
            }
            else
            {
                Check(size / 2, x, y);
                Check(size / 2, x + size / 2, y);
                Check(size / 2, x, y + size / 2);
                Check(size / 2, x + size / 2, y + size / 2);
            }
        }

        public static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            
            int N = int.Parse(Console.ReadLine());
            arr = new int[N, N];
            for(int i = 0; i < N; i++)
            {
                string[] input = Console.ReadLine().Split();
                for(int j = 0; j < N; j++)
                {
                    arr[i, j] = int.Parse(input[j]);
                }
            }
            Check(N, 0, 0);
            Console.WriteLine(white);
            Console.WriteLine(blue);
        }
    }
}

• 후기

분할정복을 배웠다...!

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

• 문제

• 문제풀이

분할정복(divide and conquer) 알고리즘을 사용하여, 2^n 크기의 배열에서 두 번째로 작은 값을 찾는 문제를 해결하는 코드입니다.

이 문제는 큰 배열을 작은 크기의 4개의 배열로 나눈 뒤, 각각의 배열에서 두 번째로 작은 값을 찾는 과정을 반복하여 해결합니다. 따라서, 재귀함수를 사용하여 문제를 풀어나갑니다.

half는 현재 구역을 4개의 구역으로 분할하기 위해 사용되는 변수입니다. winners는 각각의 구역에서 뽑힌 사람들의 추첨번호를 저장하는 배열이며, count는 winners 배열에 저장된 사람의 수를 나타냅니다.

• 코드 1

using System;

class MainClass
{
    static int[][] arr;

    static int Check(int x, int y, int size)
    {
        if (size == 1)
        { 
            return arr[x][y];
        }

        int half = size / 2;
        int[] square = new int[4];
        int count = 0;

        square[count++] = Check(x, y, half);
        square[count++] = Check(x, y + half, half);
        square[count++] = Check(x + half, y, half);
        square[count++] = Check(x + half, y + half, half);

        Array.Sort(square);

        return square[1];
    }

    static void Main()
    {
        int n = int.Parse(Console.ReadLine());

        arr = new int[n][];
        for (int i = 0; i < n; i++)
        {
            arr[i] = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        }

        int result = Check(0, 0, n);
        Console.WriteLine(result);
    }
}

• 후기

분할정복을 배웠다...!

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

• 문제

• 문제풀이

기본적으로 KMP알고리즘을 사용해주고 패턴과 입력값이 같을때마다 count++해주고 시작 인덱스를 두번째 출력으로 찍어야하기 때문에 StringBuilder에 저장해준다.

이후 count와 StringBuilder에 저장되었던 값을 차례로 입력해준다.

• 코드 1

using System;
using System.Text;

class GFG
{
    public StringBuilder sb=new StringBuilder();
    void KMPSearch(string pat, string txt)
    {
        int M = pat.Length;
        int N = txt.Length;
        int count = 0;
        int[] lps = new int[M];
        int j = 0;


        computeLPSArray(pat, M, lps);

        int i = 0;
        while (i < N)
        {
            if (pat[j] == txt[i])
            {
                j++;
                i++;
            }
            if (j == M)
            {
                count++;
                sb.Append((i - j+1)+" ");
                j = lps[j - 1];
            }

            // mismatch after j matches
            else if (i < N && pat[j] != txt[i])
            {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
        Console.WriteLine(count);
        Console.WriteLine(sb.ToString());
    }

    void computeLPSArray(string pat, int M, int[] lps)
    {

        int len = 0;
        int i = 1;
        lps[0] = 0;


        while (i < M)
        {
            if (pat[i] == pat[len])
            {
                len++;
                lps[i] = len;
                i++;
            }
            else
            {

                if (len != 0)
                {
                    len = lps[len - 1];


                }
                else
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }


    public static void Main()
    {
        string txt = Console.ReadLine();
        string pat = Console.ReadLine();
        new GFG().KMPSearch(pat, txt);
    }
}

• 후기

첫 플래티넘 문제 재밌다 이틀걸렸다...

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

• 문제

• 문제풀이

이러한 패턴을 가진 수열은 재귀함수를 사용해도 되고 값들을 다 정해준뒤 출력해도 된다.

• 코드 1(함수 만들기)

namespace YONGYONG2
{
    internal class Program
    {
        public static int Factorial(int num)
        {
            int result = 1;
            for(int i=2;i<=num;i++)
            {
                result*= i;
            }
            return result;
        }
        static void Main(string[] args)
        {
            int N=int.Parse(Console.ReadLine());
            if (N == 0||N==1)
            {
                Console.WriteLine(1);
            }
            if (N > 1)
            {
                Console.WriteLine(Factorial(N));
            }
        }
    }
}

• 코드 2(재귀함수)

namespace YONGYONG2
{
    internal class Program
    {
        public static int Factorial(int num)
        {
            if (num <= 1) return 1;
            return num*Factorial(num-1);
        }
        static void Main(string[] args)
        {
            int N=int.Parse(Console.ReadLine());

                Console.WriteLine(Factorial(N));
            
        }
    }
}

• 코드 3

namespace YONGYONG2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N=int.Parse(Console.ReadLine());
            int answer = 1;
            if (N == 0||N==1)
            {
                Console.WriteLine(1);
            }
            if (N > 1)
            {
                for(int i=2;i<=N; i++)
                {
                    answer = answer * i;
                }
                Console.WriteLine(answer);
            }
        }
    }
}

• 후기

방법이 되게 많은 것 같다.

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

• 문제

• 문제풀이

이러한 패턴을 가진 수열은 재귀함수를 사용해도 되고 값들을 다 정해준뒤 출력해도 된다.

• 코드 1

namespace ConsoleApp21
{
    internal class Program
    {
        public static int Blood(int num)
        {
            if (num == 1)
            {
                return 0;
            }
            else if (num == 2 || num == 3)
            {
                return 1;
            }
            else { 
                return Blood(num-1)+Blood(num-2);
            }
            
        }
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            Console.WriteLine(Blood(N+1));
        }
    }
}

• 코드 2

using System;

namespace ConsoleApp21
{
    internal class Program
    {
        
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] arr=new int[21];
            arr[0] = 0;
            arr[1] = 1;
            arr[2] = 1;
            
               for(int i=3;i<=N;i++)
                {
                    arr[i] = arr[i - 1] + arr[i - 2];
                }
            
            Console.WriteLine("{0}", arr[N]);
        }
    }
}

• 후기

뭔가 더 쉬운 방법이 있을거같은데...

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

• 문제

• 문제풀이

첫번째 줄에서 N을 받아 N이 0이 되도록 5와 3으로 나누고 카운트를 추가해준다. 만일 0으로 나누어 떨어지지 않는다면  -1을 출력하도록 한다.

※수정 최근 브루트포스 알고리즘을 배운 후 이 문제에 적용할 수 있음을 알게 되었다.

• 코드 1

namespace BaekJoon
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            
            int a = 0;
            while (N > 0)
            {
                if (N % 5 == 0)
                {
                    N -= 5;
                    a++;
                }
                else if (N % 3 == 0)
                {
                    N -= 3;
                    a++;
                }
                else if (N > 5)
                {
                    N-=5;
                    a++;
                }
                else
                {
                    a = -1;
                    break;
                }
                
            }
            if (a != 0)
            {
                Console.Write(a);
            }
        }
    }
}

• 코드 2(브루트 포스 알고리즘)

using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine()); // 입력값

        int minCount = int.MaxValue; // 최소한의 봉지 개수를 저장할 변수, 최대값으로 초기화

        for (int i = 0; i <= n / 3; i++) // 3kg 봉지의 개수
        {
            for (int j = 0; j <= n / 5; j++) // 5kg 봉지의 개수
            {
                int sum = 3 * i + 5 * j; // 사용한 봉지의 무게 합산

                if (sum == n) // 정확히 nkg의 설탕을 배달한 경우
                {
                    int count = i + j; // 봉지의 개수 계산

                    if (count < minCount) // 최소값 갱신
                    {
                        minCount = count;
                    }
                }
            }
        }

        if (minCount == int.MaxValue) // 봉지를 사용해도 정확히 nkg을 만들지 못한 경우
        {
            Console.WriteLine("-1");
        }
        else // 봉지를 사용하여 정확히 nkg을 만들었을 경우
        {
            Console.WriteLine(minCount);
        }
    }
}

• 후기

조건문을 잘 활용해야 풀 수 있는 것 같다.

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

• 문제

• 문제풀이

3중 for문을 사용하고 각 자리의 경우의 수가 겹치지 않게 범위를 설정해준다. 처음에는 조건문을 통해 겹치지 않게 했었다.

using System;

internal class Program
{
    
    public static void Main()
    {
        string[] input1 = Console.ReadLine().Split();
        string[] input2 = Console.ReadLine().Split();
        int sum = 0;
        int temp = 0;
        for(int i = 0; i < int.Parse(input1[0]); i++)
        {
            for(int j = 0; j < int.Parse(input1[0]); j++)
            {
                for(int k = 0; k < int.Parse(input1[0]); k++)
                {
                    if (int.Parse(input2[i]) != int.Parse(input2[j])&&int.Parse(input2[j]) != int.Parse(input2[k]) && int.Parse(input2[i]) != int.Parse(input2[k]))
                    {
                        temp = int.Parse(input2[i]) + int.Parse(input2[j]) + int.Parse(input2[k]);
                    }
                    if (sum <= temp && temp <= int.Parse(input1[1]))
                    {
                        sum = temp;
                    }
                }
            }
        }
        Console.WriteLine(sum);
    }
}

하지만 이렇게 하는 것보다 for문에서 범위를 제한하는것이 속도가 더 빠르게 나왔다.

• 코드 1

using System;

internal class Program
{
    
    public static void Main()
    {
        string[] input1 = Console.ReadLine().Split();
        string[] input2 = Console.ReadLine().Split();
        int sum = 0;
        int temp = 0;
        for(int i = 2; i < int.Parse(input1[0]); i++)
        {
            for(int j = 1; j < i; j++)
            {
                for(int k = 0; k < j; k++)
                {                  
                        temp = int.Parse(input2[i]) + int.Parse(input2[j]) + int.Parse(input2[k]);
                    if (sum <= temp && temp <= int.Parse(input1[1]))
                    {
                        sum = temp;
                        break;
                    }
                }
            }
        }
        Console.WriteLine(sum);
    }
}

• 후기

프로그래밍에 신경쓸게 아니라 수학적인 고민도 많이 필요할 것 같다.

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

• 문제

• 문제풀이

665서부터 수를 1씩 올려주며 666이 나올때 카운팅을 해준다.

• 코드 1

using System;

class MainClass {
  public static void Main (string[] args) {
    int n = int.Parse(Console.ReadLine());
    int num = 665; // 666부터 시작하기 위해 -1 처리한 값
    int count = 0;

    while (count < n) {
      num++;

      if (num.ToString().Contains("666")) {
        count++;
      }
    }

    Console.WriteLine(num);
  }
}

• 후기

C로 풀었으면 복잡했을게 C#이라 금방 풀린것같다.