용용코딩

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

• 문제풀이

열심히 종이에 적다보니 규칙을 찾게 되었다.

∑nCr*(m-1)^(n-r)이 브실이가 근무를 하는 경우의 수임을 알게 되었다.

그래서  브실이가 들어가는 경우의 수를 모두 합하여 구하려고 했으나 시간초과가 걸렸다.

# -*- coding: utf-8 -*-
import sys
MOD = 1000000007

def calculate_sigma(N, M):
    result = 0
    combination_values = [0] * (N + 1)
    exponent_values = [0] * (N + 1)
    
    combination_values[0] = 1
    exponent_values[0] = 1
    
    for R in range(1, N + 1):
        # 조합 계산에서 나눗셈을 정수 나눗셈으로 변경
        combination_values[R] = (combination_values[R - 1] * (N - R + 1) // R)
        exponent_values[R] = (exponent_values[R - 1] * (M - 1))
    
    for R in range(1, N + 1):
        result = (result + combination_values[R] * exponent_values[N - R])
    
    # 최종 결과에서 모듈러 연산
    result %= MOD
    
    return result

N, M = map(int, sys.stdin.readline().split())

sigma_result = calculate_sigma(N, M)
sys.stdout.write(str(sigma_result % MOD) + '\n')

시간초과를 해결하기 위해서는 브실이가 근무를 투입하는 경우의 수가 아니라 브실이가 근무를 들어가지 않는 수를 구해야했다.

이는 수식으로 M^N - (M-1)^N 로 나타낼 수 있다.

• 코드 1

# -*- coding: utf-8 -*-


MOD = 1000000007  # 나눌 모듈러 값

# 필요한 모듈 import
import sys

# 입력 받기
N, M = map(int, sys.stdin.readline().split())

# M^N - (M-1)^N 계산
result = (pow(M, N, MOD) - pow(M - 1, N, MOD)) % MOD

# 결과 출력
sys.stdout.write(str(result) + '\n')

• 후기

규칙을 찾아 수식으로 만들어내는 과정이 재밌던 문제이다.

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

• 문제풀이

조합을 이용해서 풀어낸다.

• 코드 1

using System;

class Program
{
    const long mod = 987654321;

    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        n = n / 2;
        long[] memo = new long[n + 1];
        memo[0] = 1;

        for (int i = 1; i <= n; i++)
        {
            memo[i] = 0;
            for (int k = 0; k < i; k++)
            {
                memo[i] += ((memo[k] % mod) * (memo[i - 1 - k] % mod)) % mod;
            }
            memo[i] %= mod;
        }

        Console.WriteLine(memo[n] % mod);
    }
}

• 후기

통계는 언제나 자주 사용되는 것 같다.

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

• 문제풀이

동적계획법을 사용하여 계산해준다.

두가지의 경우로 나눌 수 있다.

1경우: 1칸, 2칸, 4칸(두칸 가고 한칸 건너띄기)

2경우: 1칸, 3칸(한칸 가고 한칸 건너띄기)

• 코드 1

using System;

class MainClass
{
    public static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] stairs = new int[n + 1];
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++)
        {
            stairs[i] = int.Parse(Console.ReadLine());
        }

        dp[1] = stairs[1];
        if (n >= 2)
            dp[2] = stairs[1] + stairs[2];

        for (int i = 3; i <= n; i++)
        {
            dp[i] = Math.Max(dp[i - 2] + stairs[i], dp[i - 3] + stairs[i - 1] + stairs[i]);
        }

        Console.WriteLine(dp[n]);
    }
}

• 후기

동적계획법은 문제가 어느정도 정형화된 느낌이다.

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

• 문제풀이

동적계획법을 사용하여 계산해준다.

두가지의 경우로 나눌 수 있다.

1경우: 1칸, 2칸, 4칸(두칸 가고 한칸 건너띄기)

2경우: 1칸, 3칸(한칸 가고 한칸 건너띄기)

• 코드 1

n = int(input())
stairs = [0] 
dp = [0] * (n + 1)

for _ in range(n):
    stairs.append(int(input()))

dp[1] = stairs[1]
if n >= 2:
    dp[2] = stairs[1] + stairs[2]

for i in range(3, n + 1):
    dp[i] = max(dp[i - 2] + stairs[i], dp[i - 3] + stairs[i - 1] + stairs[i])

print(dp[n])

• 후기

동적계획법은 문제가 어느정도 정형화된 느낌이다.

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

• 문제풀이

람다 값을 지정해서 집합에 넣고 빼준다.

• 코드 1

N = int(input())
time_list = []
for i in range(N):
    Si, Fi = map(int, input().split())
    time_list.append((Si, Fi))

time_list.sort(key=lambda x: (x[1], x[0]))

count = 0
time = 0
for i in range(N):
    if time <= time_list[i][0]:
        count += 1
        time = time_list[i][1]

print(count)

• 후기

파이썬을 연습하는 단계이다.

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

• 문제풀이

enter인 경우  집합에 넣고 leave인 경우 직원 명단에서 빼준다.

• 코드 1

#-*- coding: utf-8 -*-

from collections import deque

n = int(input())  # 출입 기록의 개수

employees = set()  # 직원 명단을 저장할 집합(set) 생성

for _ in range(n):
    record = input().split()
    name, status = record[0], record[1]

    if status == "enter":
        employees.add(name)  # enter인 경우 직원 명단에 추가
    else:
        employees.remove(name)  # leave인 경우 직원 명단에서 제거

# 직원 명단을 알파벳 역순으로 정렬하여 출력
for employee in sorted(employees, reverse=True):
    print(employee)

• 후기

파이썬을 연습하는 단계이다.

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

• 문제

• 문제풀이

처음에는 문제에서 요구하는 그대로 작성했다가 시간초과가 발생했다.

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

namespace QueueStackSimulation
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] structureTypes = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] structureData = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            List<Queue<int>> queues = new List<Queue<int>>();
            List<Stack<int>> stacks = new List<Stack<int>>();
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < N; i++)
            {
                if (structureTypes[i] == 0)
                {
                    Queue<int> queue = new Queue<int>();
                    queue.Enqueue(structureData[i]);
                    queues.Add(queue);
                }
                else
                {
                    Stack<int> stack = new Stack<int>();
                    stack.Push(structureData[i]);
                    stacks.Add(stack);
                }
            }

            int M = int.Parse(Console.ReadLine());
            int[] insertData = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            foreach (int data in insertData)
            {
                int result = -1; // Default value

                for (int i = 0; i < N; i++)
                {
                    if (queues.Count > i && queues[i].Count > 0)
                    {
                        result = queues[i].Dequeue();
                    }
                    else if (stacks.Count > i && stacks[i].Count > 0)
                    {
                        result = stacks[i].Pop();
                    }

                    if (result == data)
                    {
                        sb.Append(result + " ");
                        break;
                    }
                }
            }

            Console.WriteLine(sb.ToString().Trim());
        }
    }
}

스택은 처음 숫자가 그대로 남고 큐만 숫자가 변동 된다는 것을 알게 되었다. 따라서 스택은 무시하고 큐의 규에만 집중하여 코드를 짜면 해결할 수 있다.

• 코드 1

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

namespace CodeConversion
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int[] sequence_A = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] sequence_B = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int M = int.Parse(Console.ReadLine());
            int[] sequence_C = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            StringBuilder sb = new StringBuilder();
            Queue<int> queue = new Queue<int>();
            for (int i = N - 1; i >= 0; i--)
            {
                if (sequence_A[i] == 0)
                {
                    queue.Enqueue(sequence_B[i]);
                }
            }



            for (int i = 0; i < M; i++)
            {
                queue.Enqueue(sequence_C[i]);
                sb.Append(queue.Dequeue() + " ");
            }
            Console.WriteLine(sb.ToString());

        }
    }
}

• 후기

더 좋은 코드로 만들기 위해 손으로 직접해보는 것은 중요한 것 같다.

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

• 문제

• 문제풀이

100칸짜리 맵을 만든 뒤 BFS방식을 사용하여 탐색을 한 후에 최소 횟수를 출력한다.

• 코드 1

using System;
using System.Collections.Generic;
using System.Linq;

class SnakeAndLadderGame
{
    static void Main(string[] args)
    {
        List<int> ladderOrSnake = new List<int>(101);
        for (int i = 0; i <= 100; i++)
        {
            ladderOrSnake.Add(-1);
        }


        string[] input = Console.ReadLine().Split(' ');
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        for (int i = 0; i < N + M; i++)
        {
            int[] data = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            if (data[0] < data[1])
            {
                ladderOrSnake[data[0]] = data[1];
            }
            else
            {
                ladderOrSnake[data[0]] = data[1];
            }
        }

        int[] dist = new int[101];
        for (int i = 0; i <= 100; i++)
        {
            dist[i] = -1;
        }
        dist[1] = 0;

        Queue<int> queue = new Queue<int>();
        queue.Enqueue(1);

        while (queue.Count > 0)
        {
            int curPos = queue.Dequeue();

            for (int i = 1; i <= 6; i++)
            {
                int nextPos = curPos + i;
                if (nextPos <= 100 && ladderOrSnake[nextPos] != -1)
                {
                    nextPos = ladderOrSnake[nextPos];
                }

                if (nextPos <= 100 && dist[nextPos] == -1)
                {
                    dist[nextPos] = dist[curPos] + 1;
                    queue.Enqueue(nextPos);
                }
            }
        }

        Console.WriteLine(dist[100]);
    }
}

• 후기

그래프를 활용한 방식은 까먹지 않게 자주자주 해야겠다.