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

문제

다들 문제 제목을 보고 요즘 가장 핫한 영화를 생각했겠지만 이 이야기는 LUL(League Us Legends) 게임에서 아이언(Iron) 티어에 있는 형동이의 슬픈 이야기이다. LUL에서 티어는 게임 실력을 판가름할 수 있는 지표이다. 그중 아이언 티어는 가장 낮은 단계에 위치해 있다. 친구인 강엽이와 건홍이에게 “Iron man”이라며 게임을 못한다고 놀림당하던 형동이는 꼭 아이언 티어에서 벗어나겠다고 결심했다. 하지만 형동이는 자신의 실력으로 절대 아이언(Iron) 티어에서 벗어나지 못하는 것을 알고 있다. LUL은 두 명의 플레이어가 같이 팀이 되어하는 게임이기 때문에 자신이 못해도 게임에서 이길 수 있고 자신이 잘해도 게임은 질 수 있다. 형동이는 게임은 못하지만 머리가 매우 똑똑하여 LUL 게임을 해킹하여서 몇몇 플레이어와 같이 게임을 하게 되면 게임의 승패가 어떻게 되는지 알게 되었다. 하지만 해킹을 통하여 알아내지 못한 플레이어와 같이 게임을 하는 경우 형동이가 매우 못하기 때문에 같은 팀원이 아무리 잘해도 반드시 진다.

위와 같은 경우에서 “JIHOON”과 같이 게임을 하는 경우 20점( W = 20)을 획득하는 반면에 “GANGYEOP”이나 “MINSUNG”과 같이 게임 하는 경우 경우 15점(L = 15)을 잃게 된다. 뿐만 아니라, 해킹을 통해 알지 내지 못한 플레이어를 만나게 되는 경우 형동이가 매우 못하여지기 때문에 15점을 잃게 된다. (단, 계속 지더라도 점수는 0점 밑으로 떨어지지 않는다.)

형동이가 N번에 게임을 통해서 아이언 티어에서 탈출한 경우 형동이는 “I AM NOT IRONMAN”이라고 IRONMAN”이라고 외치지만 탈출하지 못한 경우 “I AM IRONMAN”이라고 외친다.

여기서 아이언 티어를 탈출하기 위해서 100점 (G = 100) 이상이 되어야 했다면 9번째 게임(주황색 사각형)을 하고 아이언 티어를 탈출하였기 때문에 형동이는 “I AM NOT IRONMAN”이라고 외친다. 아이언 티어에서 탈출한 경우 그 이후에 게임은 신경 쓰지 않는다.

하지만 만약 탈출하기 위해서 200점(G = 200) 이상이 되어야 한다고 했을 경우 형동이는 아이언 티어를 탈출하지 못했기 때문에 “I AM IRONMAN”이라고 외치게 된다.

과연 형동이는 게임이 끝난 후 어떤 대사를 할 지 우리가 맞춰보자.

입력

출력

코드

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main()
{
	int N, P;
	vector<string> list;
	int W, L, G;
	cin >> N >> P;
	cin >> W >> L >> G;
	for (int i = 0; i < P; i++)
	{
		string name, seng;
		cin >> name >> seng;
		if (seng == "W") list.push_back(name);
	}

	int score = 0;

	for (int i = 0; i < N; i++)
	{
		string name;
		cin >> name;
		bool check = false;
		for (int i = 0; i < list.size(); i++)
		{
			if (name == list.at(i))
			{
				check = true;
				score += W;
				if (score >= G)
				{
					cout << "I AM NOT IRONMAN!!";
					return 0;
				}
			}
		}
		if (check == false)
		{
			if (score <= L) score = 0;
			else score -= L;
		}
	}
	cout << "I AM IRONMAN!!";

}

https://school.programmers.co.kr/learn/courses/30/lessons/135807

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

1. array들을 set를 사용해 중복을 제거합니다.
2. arrayA, arrayB 각각의 gcdA, gcdB 를 구합니다.

3-1. arrayA를 gcdB로 나눠지면 gcdB를 0으로 바꿉니다.

3-2. arrayB를 gcdA롤 나눠지면 gcdA를 0으로 바꿉니다.

4 max(gcdA, gcdB)를 해서 값을 반환합니다.

코드

from math import gcd

def solution(arrayA,arrayB):
    answer = 0
    arrayA = list(set(arrayA))
    arrayB = list(set(arrayB))
    gcdA, gcdB = arrayA[0], arrayB[0]
    for i,j in zip(arrayA, arrayB):
        gcdA = gcd(gcdA,i)
        gcdB = gcd(gcdB,j)

    for i,j in zip(arrayA, arrayB):
        if gcdB != 0 and i % gcdB == 0 :
            gcdB = 0
        if gcdA != 0 and j % gcdA == 0:
            gcdA = 0

    return max(gcdA, gcdB)

https://school.programmers.co.kr/learn/courses/30/lessons/140107

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

1. 0부터 d까지 간격은 k로 반복합니다.

2. 원의 좌표 공식을 이용해서 temp = (d^2 - i^2)^0.5 를 구합니다.

3. temp를 k로 나눈 몫에 1을 더하여 answer에 더합니다. 

-> answer += temp//k + 1

4. answer을 반환합니다.

밑에 사진은 k=2, d=7 입니다. i =2 일때 예시를 들었습니다.

i = 2 일때 k 간격만큼 유지하면서 점의 갯수는 위의 3번의 식입니다.

정리하면 temp//k + 1 입니다.

코드

import math

def solution(k, d):
    answer = 0
    for i in range(0,d+1,k):
        temp =math.isqrt(pow(d, 2) - pow(i, 2))
        answer += temp//k + 1
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/132266

문제

입출력

제한사항

풀이방법

결론부터 말하자면, 다익스트라와 플로이드-워셜 알고리즘은 시간초과가 발생해서 BFS로 풀었습니다.

1. 그래프를 입력합니다.

2. 각각의 노드의 거리를 -1로 초기화합니다.

3. 도착지에서부터 출발지까지의 거리를 BFS를 이용해 계산합니다.

-> BFS를 사용할 수 있는 이유는 간선의 거리가 모두 1이므로 최소경로 알고리즘을 사용하지 않아도 됩니다.

4. sources에서 destination 거리를 costs배열에서 구해서 추가합니다.

코드

from collections import deque

def bfs(destination, graph, costs):
	# 도착지에서부터 출발지까지의 거리를 계산
    q = deque([destination])
    costs[destination] = 0
    while q:
        x = q.popleft()
        for node in graph[x]:
            if costs[node] == -1:
                costs[node] = costs[x] + 1
                q.append(node)
    return costs
    
def solution(n, roads, sources, destination):
	# 그래프 추가
    graph = [[] for _ in range(n + 1)]
    for start, end in roads:
        graph[start].append(end)
        graph[end].append(start)
    costs = [-1] * (n + 1)
    costs = bfs(destination, graph, costs)

    return [costs[s] for s in sources]

결론

최소거리라는 식만보고 다익스트라를 이용해 풀어서 시간초과가 발생했습니다.

이후 플로이드 워셜을 풀었는데 이것은 시간복잡도 n^3이었지만 혹시나 풀어봤습니다. 하지만 시간초과가 발생했습니다.

BFS를 이용해 시간초과가 발생하지 않았습니다.

다들 BFS로 풉시다!

https://school.programmers.co.kr/learn/courses/30/lessons/138476

문제

입출력

제한사항

풀이방법

1. Counter 라이브러리의 most_common을 사용합니다.

-> counter가 많이 나온 순서대로 정렬하여 list 형식으로 반환합니다.

2. 가장 많이 나온 숫자들부터 k-= 많이 나온 수의 횟수 반복합니다.

3. k  < 1인 경우가 되었을 때,   횟수 반복을 몇 번 했는지 기록하고 수를 반환합니다.

코드

from collections import Counter

def solution(k, tangerine):
    counter = Counter(tangerine).most_common()
    answer = 0
    for i in counter:
        if k <  1:
            break
        k -= i[1]
        answer += 1
    return answer

결론

그리디 알고리즘으로 많이 나온 수를 정렬합니다.

많이 나온 수부터 천천히 뺀다면 답이 나옵니다.

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

문제

강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다.

숫자 1, 2, 7, 8, 9를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요?

강민이는 이 문제의 답이 207(78 + 129)이라고 생각했다. 그런데 선생님은 책 4페이지에 있는 비슷한 문제를 모두 풀어오라는 숙제를 내셨다. 

작년부터 프로그래밍을 시작한 강민이는 이런 숙제보다 코딩을 더 재밌어했다. 그래서 강민이는 이 숙제를 코딩으로 해결하기로 했다!

어린 강민이를 위해 코딩을 도와주자.

풀이방법

풀이방법은 간단합니다.

1. 숫자들을 정렬합니다.

-> 정렬해야 작은 수가 큰 자릿수를 차지하기 때문에 덧셈을 했을 때, 작은 수가 나옵니다.

2. 모든 0을 index가 0의 개수 + 2에 해당하는 index에 모두 넣습니다.

3. 숫자의 길이가 짝수인지 홀수인지 구합니다.

3-1. 짝수인 경우 a,b 배열에 맨 앞의 숫자 하나씩 넣습니다.

3-2. 홀수인 경우, a 배열에 0번째 index,를 넣은 뒤, a, b 배열에 번갈아 숫자를 넣습니다.

짝수인 경우

1 3 0 0 2 6

(정렬)

0 0 1 2 3 6

(0을 뒤로 넘김)

1 2 0 0 3 6

a배열 1 0 3, b 배열 2 0 6

-> 309

홀수인 경우

1 3 0 0 0 2 6

(정렬)

0 0 0 1 2 3 6

(0을 뒤로 넘김)

1 2 0 0 0 3 6

a배열 1 0 0 6 b  배열 2 0 3

->1209

코드

import sys
from collections import deque

while True:
    arr = deque(map(int, sys.stdin.readline().rstrip().split()))
    if arr[0] == 0:
        break
    arr.popleft()
    # 정렬
    arr = sorted(arr)
    zeros = 0
    for i in arr:
        if i == 0:
            zeros += 1
        else:
            break
    for i in range(zeros):
        arr.pop(0)
    for i in range(zeros):
        arr.insert(2,0)

    a, b = [], []
    if len(arr)% 2 == 0:
        for i in range(len(arr)):
            if i % 2 == 0:
                a.append(arr[i])
            else:
                b.append(arr[i])
        print(int("".join(map(str,a)))+ int("".join(map(str,b))))
    else:
        a.append(arr[0])
        for i in range(1,len(arr)):
            if i % 2 == 1:
                a.append(arr[i])
            else:
                b.append(arr[i])
        print(int("".join(map(str,a)))+ int("".join(map(str,b))))

결론

0을 뒤로 넘기는 것, 짝수와 홀수일때 수를 넘기는 것과 str, int 형변환만 잘한다면 바로 풀리는 문제입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/181186

문제

더보기

정우는 예술적 감각이 뛰어난 타일공입니다. 그는 단순한 타일을 활용하여 불규칙하면서도 화려하게 타일링을 하곤 합니다.

어느 날 정우는 가로 길이 n, 세로 길이 3 인 판을 타일링하는 의뢰를 맡았습니다. 아방가르드한 디자인 영감이 떠오른 정우는 다음과 같은 두 가지 종류의 타일로 타일링을 하기로 결정했습니다.

각 타일은 90도씩 회전할 수 있으며 타일의 개수는 제한이 없습니다.

n이 주어졌을 때, 이 두 가지 종류의 타일로 n x 3 크기의 판을 타일링하는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

입출력( + 추가적인 Test Case)

제한사항

풀이방법

정말 정말 힘들었습니다.... 정말 힘들었어요.. 정말로... 이상한 패턴 찾느라 고생했습니다...

이러한 패턴들을 찾아낸 뒤, dp를 이용해 풀었습니다.

n <= 6 일 때까지 값을 각각 dp 배열과 sum_dp 배열을 만들어 준뒤 n >= 7 부터 반복문을 통해 계산했습니다.

dp[n]에 대해 n-1, n-2, n-3 은 각각 1, 2, 5를 곱해서 더해주면 됩니다. 하지만 n-4, n-5, n-6은 계속 unique한 모양이 생깁니다. n = 7일 때, n=4 인 경우에 1*3막대를 가운데에 추가해야하기 때문입니다.

다시 말해서 3의 배수로 unique한 패턴이 생기기 때문에 누적 합을 저장할 배열(sum_dp) 필요합니다.

그래서 sum_dp[i] 는 dp[i]와 3의 배수로 증가하는 unique한 타일인 sum_dp[i-3]을 더해주면서 저장해줍니다.

코드

def solution(n):
    dp = [0 for _ in range(100001)]
    
    # 누적 합
    sum_dp = [0 for _ in range(100001)]

    sum_dp[1] = 1
    sum_dp[2] = 3
    sum_dp[3] = 11
    sum_dp[4] = 24
    sum_dp[5] = 65
    sum_dp[6] = 181

    dp[1] = 1
    dp[2] = 3
    dp[3] = 10
    dp[4] = 23
    dp[5] = 62
    dp[6] = 170

    for i in range(7, n+1):
    	
        dp[i] = dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 5 + sum_dp[i - 4] * 2 + sum_dp[i - 5] * 2 + sum_dp[i - 6] * 4
        dp[i] = dp[i] % 1000000007
		
        # 누적 합 계산
        sum_dp[i] = dp[i] + sum_dp[i-3]
        sum_dp[i] = sum_dp[i] % 1000000007
    return dp[n]

결론

어렵다. 진짜 어렵다... 누적 합에 대해 다시 공부하거나 점화식에 대해 공부해봐야겠다.