용용코딩

• 문제

입력

• 문제풀이

기본적으로 BFS(넓이우선탐색)을 사용하였다. 큐에 넣고 조건에 맞다면 dx, dy에 의해 지정된칸으로 이동후 다시 탐색과정을 거친다. 최종적으로 가장높은 숫자가 미로의 출구이다.

• 코드 1

using System;
using System.Collections.Generic;

class Program
{
    public static int[,] graph = new int[50, 50];
    public static int[] dx = { -1, 1, 0, 0, 1, 1, -1, -1 };
    public static int[] dy = { 0, 0, 1, -1, 1, -1, -1, 1 };
    public static int[] moveRow;
    public static int[] moveCol;
    public static string[] maze;
    public static Queue<(int, int)> queue = new Queue<(int, int)>();
    public static int num;

    static void Main(string[] args)
    {
        string[] maze = {
            ".......",
            "X.X.X..",
            ".......",
            "....X..",
            "X....X.",
            "......."
            /*"...",
            "...",
            "..."*/
            /*"X.X",
            "...",
            "XXX",
            "X.X"*/
            //"..X.X.X.X.X.X."
        };

        int startRow = 5;
        int startCol = 0;
        int[] moveRow = new int[] { 1, 0, -1, 0, -2, 1 };
        int[] moveCol = new int[] { 0, -1, 0, 1, 3, 0 };

        for (int i = 0; i < maze.Length; i++)
        {
            for (int j = 0; j < maze[0].Length; j++)
            {
                graph[i, j] = -1;
            }
        }

        graph[startRow, startCol] = 0;
        queue.Enqueue((startRow, startCol));

        while (queue.Count > 0)
        {
            (int a, int b) = queue.Dequeue();

            for (int k = 0; k < moveRow.Length; k++)
            {
                int y = a + moveRow[k];
                int x = b + moveCol[k];
                if (y >= 0 && y < maze.Length && x >= 0 && x < maze[0].Length)
                {
                    if (maze[y][x] == '.' && graph[y, x] == -1)
                    {
                        graph[y, x] = graph[a, b] + 1;
                        queue.Enqueue((y, x));
                    }
                }
            }
        }

        /* 확인하기
        for (int i = 0; i < maze.Length; i++)
        {
            for (int j = 0; j < maze[0].Length; j++)
            {
                if (i == startRow && j == startCol)
                {
                    Console.Write($"{"start",-6}");
                }
                else Console.Write($"{graph[i, j],-6}");
            }
            Console.WriteLine();
        }
        */
        num = 0;
        for (int i = 0; i < maze.Length; i++)
        {
            for (int j = 0; j < maze[0].Length; j++)
            {
                if (maze[i].Substring(j, 1) == "." && graph[i, j] == -1)
                {
                    num = -1;
                    break;
                }
                num = Math.Max(num, graph[i, j]);
            }
        }

        Console.WriteLine(num);
    }
}

• 후기

오랜만에 BFS를 했더니 행과 열을 반대로 더해야한다는 것을 까먹었다.

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

• 문제

• 문제풀이

단어를 대문자로 변경을 해준뒤 알파벳 26개의 배열을 만들어준다. 알파벳이 몇개 쓰였는지 카운트 후 출력해준다.

• 코드 1

word = input().upper()
charAt = sorted(list(word))
count = [0] * 26
for char in charAt:
    count[ord(char) - ord('A')] += 1
maxcnt = 0
maxChar = 'A'
two = False
for i in range(26):
    if count[i] > maxcnt:
        maxcnt = count[i]
        maxChar = chr(ord('A') + i)
        two = False
    elif count[i] == maxcnt:
        two = True
if two:
    print("?")
else:
    print(maxChar)

• 후기

파이썬도 앞으로 열심히 사용해야겠다.

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

• 문제

• 문제풀이

1번 코드는 그리디 알고리즘을 활용해 풀었다. 

2번 코드는 선형방정식을 행렬로 사용해 풀 수 있다.

• 코드 1

using System;
using System.Collections.Generic;
using System.Globalization;

class Program
{

    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        bool find = false;
        for(int i = -999; i <= 999; i++)
        {

            for(int j = -999; j <= 999; j++)
            {
                if (input[0] * i + input[1] * j == input[2] && input[3] * i + input[4] * j == input[5])
                {
                    Console.WriteLine("{0} {1}", i, j);
                    find = true;
                    break;
                }
            }
            if (find)
            {
                break;
            }
        }
    }
}

• 코드 2

using System;

class Program
{
    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int a = input[0];
        int b = input[1];
        int c = input[2];
        int d = input[3];
        int e = input[4];
        int f = input[5];

        int x = (c * e - b * f) / (a * e - b * d);
        int y = (a * f - d * c) / (a * e - b * d);

        Console.WriteLine("{0} {1}", x, y);
    }
}

• 후기

공학수학으로 선형방정식의 행렬계산법을 배웠는데 이게 이렇게 쓰일 줄 몰랐다.

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

• 문제

• 문제풀이

로프가 최대로 견딜 수 있는 무게는 배열을 정렬한 후 작은것부터 무게*N-i개 이다. 반복문을 통해 max값을 최신화해준다.

• 코드 1

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Text;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] rope = new int[N];
        int sum = 0;
        int max = 0;
        for(int i = 0; i < N; i++)
        {
            rope[i] = int.Parse(Console.ReadLine());
        }
        Array.Sort(rope);
        for(int i = 0; i < N; i++)
        {
            sum = rope[i] * (N - i);
            if (sum > max)
            {
                max = sum;
            }
        }
        Console.WriteLine(max);
    }
}

• 후기

규칙을 발견해서 금방 풀 수 있었다.

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

• 문제

• 문제풀이

while문의 조건에 따라 다음과 같이 작동한다.

1.

스택:3

result:null

조건 :x -> push

2.

스택:null

result:5

조건:3<5 -> pop

3.

스택:5

result:5

조건5>2 -> push

4.

스택:5 2

result:5

조건 5<7 -> pop

5.

스택:5

result:5 7

조건 : 2<7 -> pop

6.

스택: 7

result 5 7 7

조건: stack.count>0 -> pop

7.

스택:

result 5 7 7 -1

조건:

• 코드 1

using System;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int[] result = new int[N];
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i < N; i++)
        {
            while (stack.Count > 0 && input[stack.Peek()] < input[i])
                result[stack.Pop()] = input[i];

            stack.Push(i);
        }

        while (stack.Count > 0)
            result[stack.Pop()] = -1;

        Console.WriteLine(string.Join(" ", result));
    }
}

• 후기

오랜만에 스택 문제를 풀었더니 재밌었다.

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

• 문제

• 문제풀이

W로 칠하는 개수와 B로 칠하는 개수를 각각 카운팅해준 뒤 더 적은 수를 출력해준다.

• 코드 1

using System;

namespace Baekjoon
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int n = int.Parse(input[0]);
            int m = int.Parse(input[1]);

            char[,] board = new char[n, m];

            for (int i = 0; i < n; i++)
            {
                string line = Console.ReadLine();
                for (int j = 0; j < m; j++)
                {
                    board[i, j] = line[j];
                }
            }

            int min = int.MaxValue;

            for (int i = 0; i <= n - 8; i++)
            {
                for (int j = 0; j <= m - 8; j++)
                {
                    int count1 = 0;
                    int count2 = 0;

                    for (int x = i; x < i + 8; x++)
                    {
                        for (int y = j; y < j + 8; y++)
                        {
                            if ((x + y) % 2 == 0)
                            {
                                if (board[x, y] != 'W')
                                    count1++;
                                if (board[x, y] != 'B')
                                    count2++;
                            }
                            else
                            {
                                if (board[x, y] != 'B')
                                    count1++;
                                if (board[x, y] != 'W')
                                    count2++;
                            }
                        }
                    }

                    int minCount = Math.Min(count1, count2);
                    if (minCount < min)
                        min = minCount;
                }
            }

            Console.WriteLine(min);
        }
    }
}

• 후기

처음 8x8사이즈를 어떻게 해결해야하는지 고민을 했다.

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

• 문제

• 문제풀이

(i+1)%n을 통해 다시 처음으로 돌아오는 걸 알 수 있다.

• 코드 1

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[] list = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int cnt = 0;
        
        

        for (int i = 0; i < n; i++)
        {
            if (list[i] >= list[(i + 1) % n])
            {
                cnt++;
            }
        }

        Console.WriteLine(cnt);
    }
}

• 후기

원탁을 돌리는게 너무 어려웠다.

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

• 문제

• 문제풀이

배열을 만들어서 틀린 문자열의 인덱스를 찾고 그 인덱스에 해당하는 옳은 문자열을 출력해준다.

• 코드 1

using System;

class MainClass
{
    static void Main()
    {
        string[] wrong = { "@", "[", "!", ";", "^", "0", "7", "\\\\'", "\\'" };
        string[] right = { "a", "c", "i", "j", "n", "o", "t", "w", "v" };

        int num = int.Parse(Console.ReadLine());

        for (int i = 0; i < num; i++)
        {
            string str = Console.ReadLine();
            int count = 0;

            for (int k = 0; k < str.Length; k++)
            {
                for (int j = 0; j < wrong.Length; j++)
                {
                    int ind = str.IndexOf(wrong[j]);

                    if (ind != -1)
                    {
                        str = str.Remove(ind, wrong[j].Length).Insert(ind, right[j]);
                        count++;
                        j--;
                    }
                }
            }

            if (count >= str.Length / 2.0)
                Console.WriteLine("I don't understand");
            else
                Console.WriteLine(str);
        }
    }
}

• 후기

문자열 탐색은 언제나 쉬운듯 어렵다