Willing

1. 문제 / 난이도 : Gold Ⅳ

www.acmicpc.net/problem/2572

2. 풀이 및 코드 설명

처음에는 가능한 모든 경우의 수를 다 해봐야 하나...? 라고 생각했지만 K의 최대가 10000이고, N의 최대가 1000이어서 모든 경우의 수를 돌면 10000의 1000제곱....빠르게 포기했다. 다른 방법을 생각해보았다.

그래서 그 다음 생각한 방법이 DP를 이용해 푸는 것! 다음과 같은 입력이 들어올 때로 예를 들면,

5
R G R B G
4 5
1 2 R
1 3 G
2 3 G
1 4 R
4 3 B

다섯번째 G 카드를 들고 있을 때 각각의 마을에서 얻는 점수를 계산해보면, DP 배열은 다음과 같다

그 다음, 네번째 B 카드를 들고 있을 때 1번 마을의 경우를 살펴보면 => 1번 마을에서는 2, 3, 4번 마을로 갈 수 있으므로

2번 마을로 가는 경우 = DP[5][2] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 0 = 10 + 0 = 10

4번 마을로 가는 경우 = DP[5][4] + 0 = 0 + 0 = 0

세가지 경우의 MAX값은 10이다.

(* 빨간색 숫자는 해당 마을로 움직일 때 얻는 점수, B카드를 들고 있을 때 1번에서 2번 마을로 가는 경우에는 R색의 길을 지나므로 점수를 얻기 때문에 0을 더해준다)

마찬가지로 네번째 B 카드를 들고 있을 때 4번 마을의 경우를 살펴보면 => 4번 마을에서는 1, 3번 마을로 갈 수 있으므로

1번 마을로 가는 경우 = DP[5][1] + 0 = 10 + 0 = 10

3번 마을로 가는 경우 = DP[5][3] + 10 = 10 + 10 = 20

두가지 경우의 MAX값은 20이다.

위와 같은 과정을 거쳐 DP배열은 전부 채우면, DP는 다음과 같은 형태가 된다.

원하는 것은 1번 마을에서 첫번째 카드를 들고 있을 때 얻을 수 있는 점수의 최댓값이므로 DP[1][R]이 답이된다.

(1) 설정 및 초기화

# 보드 정보 저장
for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))
# dp 배열 초기화
dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

board[i] : i에서 갈 수 있는 정점과, 그 때 지나는 길의 색이 튜플 형태로 저장되어 있음

(2) DP배열 채우기

for i in range(N-1, -1, -1): # 카드를 하나씩 돌면서
    current_card = cards[i] # 현재 카드
    for j in range(M, 0, -1): # 각 마을을 하나씩 돌면서
        temp = 0
        for k in board[j]: # 해당 마을에서 갈 수 있는 정점의 정보
            node = k[0] # 정점 번호
            vertex = k[1] # 길의 색
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp) # 모든 경우의 최댓값
        dp[i][j] = temp

3. 전체 코드

import sys

N = int(input())
cards = sys.stdin.readline().split()
M, K = map(int, sys.stdin.readline().split())
board = [[] for _ in range(M + 1)]

for _ in range(K):
    i, j, c = sys.stdin.readline().split()
    board[int(i)].append((int(j), c))
    board[int(j)].append((int(i), c))

dp = [[0 for _ in range(M + 1)] for _ in range(N+1)]

for i in range(N-1, -1, -1):
    current_card = cards[i]
    for j in range(M, 0, -1):
        temp = 0
        for k in board[j]:
            node = k[0]
            vertex = k[1]
            temp = max(dp[i+1][node] + (10 if vertex == current_card else 0), temp)
        dp[i][j] = temp
print(dp[0][1])

1. 문제 / 난이도 : Gold Ⅴ

www.acmicpc.net/problem/1092

2. 풀이 및 코드 설명

하... 분명히 틀린 부분이 없는데 계속 시간초과가 나서 PyPy3로 제출해보니 맞았다...앞으로는 PyPy3로 제출하자....

무거운 화물을 들 수 있는 크레인에게 무거운 화물을 옮기게 하자! 만 기억하면 쉽게 풀리는 문제. 무게 제한이 높은 크레인에게 현재 남아 있는 화물 중 가장 무거운 것을 들게 해야 모든 박스를 옮기는 최소 시간이 나온다.

간단한 코드이기 때문에 코드 블락 단위 설명은 생략.

3. 전체 코드

import sys
N = int(input())
limits = map(int, sys.stdin.readline().split()) # 크레인 별 무게 제한
M = int(input())
packages = map(int, sys.stdin.readline().split()) # 화물 별 무게

# 무게 제한과 화물 무게 전부 내림차순으로 정렬
limits = sorted(limits, reverse=True)
packages = sorted(packages, reverse=True)

# 무게 제한이 제일 높은 크레인도 제일 무거운 화물을 들 수 없는 경우
if packages[0] > limits[0] : 
    print(-1)
    exit()

answer = 0
# 화물이 전부 옮겨질 때까지
while len(packages) > 0:
    answer += 1
    # 무게제한을 돌면서 옮길 수 있는 화물을 옮김
    for l in limits:
        for j in range(len(packages)):
            if l >= packages[j]: # 화물을 옮길 수 있으면
                del packages[j]
                break
print(answer)

1. input

* 입력받아야하는 값의 개수가 엄청나게 많을 때는 시간 초과를 유발할 수 있음!!

x = input()

- 사용자에게 값을 입력받아 변수에 저장

- 모든 입력값을 문자열(string)으로 취급

x = int(input())

- 형변환을 통해 원하는 자료형으로 변환 가능

x, y = map(int, input().split())

- 위와 같은 방식으로 원하는 자료형의 데이터를 여러 개 입력 받을 수 있음

2. sys.stdin

import sys
for line in sys.stdin:
	print(line)

- 여러 줄 입력받음

3. sys.stdin.readline

import sys
N = input()
a = [sys.stdin.readline() for _ in range(N)]

- 한 줄 입력받을 때 사용

- 위와 같은 방식으로 여러 줄 입력받을 수 있음

! 입출력 속도

sys.stdin.readline > raw_input() > input()

● 2020 KAKAO BLIND RECRUITMENT 문제

● 출처 : 프로그래머스 코딩 테스트 연습, programmers.co.kr/learn/courses/30/lessons/60058

● 코드 - Python

def check(u):
    if u[0] == ")": return 0

    cnt = 0
    for i in range(len(u)):
        if cnt < 0 : return 0
        elif u[i] == "(": cnt += 1
        else: cnt -= 1
    return cnt == 0

def reverse(u):
    reversed = ""
    for i in range(len(u)):
        if u[i] == ")": reversed += "("
        else: reversed += ")"
    return reversed

def devide(v):
    u, cnt = "", 0
    if v == "": return v

    for i in range(len(v) + 1):
        if cnt == 0 and i > 0 : 
            if check(u):
                return u + devide(v[i:])
            else:
                u = u[1:-1]
                return "(" + devide(v[i:]) + ")" + reverse(u)
        elif v[i] == "(": 
            u += v[i]
            cnt += 1
        else: 
            u += v[i]
            cnt -= 1


def solution(p):
    if check(p):
        return p
    else :
        return devide(p)

- check : 문자열이 올바른 문자열인지 아닌지를 검사하는 함수. 올바른 문자열이라면 1을, 그렇지 않다면 0을 반환

- reverse : 괄호를 뒤바꾸는 함수. ) -> ( 로, ( -> ) 로 바꿔줌

- devide : 문자열을 u 부분과 v 부분으로 나누어 재귀를 도릴 수 있게 하는 함수. )와 (의 개수가 같은지를 cnt를 통해 확인하여 u, v로 분리한 후 check를 통해 해당 u가 올바른 문자열인지 아닌지를 판단하여 그에 맞게 처리

! BLOCKING POINT

1. v가 빈 문자열인 경우

• 처음 devide안의 for문에서 범위 설정을 len(v)까지로만 해주었었는데, 그 경우 for문을 다 돌고 끝날때 예외처리를 해주지 못했다.
• 즉 v가 "()"의 형태일 때 마지막 괄호를 넣음으로써 비로소 cnt가 0이 되는데, for문 밖으로 나와버리므로 안의 분기로 들어가지 못했던 것
• for문의 범위를 len(v) + 1로 함으로써 마지막 원소까지 넣은 후 한 번 더 돌 수 있게 해준 후, v = ""일 경우의 예외 분기를 추가해주었다.
• 아직 맘에 들지 않는 부분 -> 다른 방법으로 처리할 수 있는지 알아볼 것

2. "괄호를 뒤집는다"의 잘못된 이해

• 처음에는 단순히 순서를 뒤집는다는 뜻으로 이해
• u[::-1]  구문을 통해 reversed() 방식을 수행 -> 12번 부터 오답 판정
• 질문 게시판을 찾아보니 순서를 뒤집는 것이 아닌 괄호의 방향자체를 바꾸는 것이었음
• reverse라는 함수를 새로 추가해주며 해당 문제 해결