MINJU's code story

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

n = int(input())
dp = [0] * 1001

dp[0] = 1
dp[1] = 1

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

print(dp[n]%10007)

🔮 참고 링크 

https://cijbest.tistory.com/21

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

• dp,백트랙킹도 아니고 dfs,bfs도 아님
• 첨에 재귀로 구하려고 했으나 뒤에 테케에서 전부 시간 초과 걸림
• while문 돌리면서 break 조건을 len(q1) * 3과 tot1 == tot2로 해줘야 함
• len(q1) * 4 일 때가 처음으로 돌아갈 때인데, 3으로 숫자를 낮춰서 돌려봐도 통과함
• 2로 하면 안 통과

from collections import deque
def solution(queue1, queue2):
    answer = 0   
    q1, q2 = deque(queue1), deque(queue2)
    tot1, tot2 = sum(q1), sum(q2)
    total = tot1 + tot2
    limit = len(q1) * 3
    
    if total % 2 != 0:
        return -1

    while(True):
        if tot1 > tot2:
            target = q1.popleft()
            q2.append(target)
            tot1 -= target
            tot2 += target
            answer += 1
        elif tot1 < tot2:
            target = q2.popleft()
            q1.append(target)
            tot1 += target
            tot2 -= target
            answer += 1
        else:
            break
        
        if answer == limit:
            answer = -1
            break
    
    return answer

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

• 두 팀으로 나누는 조합 생성(p)
• 각각의 팀이 가지는 능력치 담은 power 배열 0으로 초기화
• 각 팀마다 2명씩 뽑아서 2명의 팀원의 능력치를 해당 power 배열에 담음
• 팀은 결국 두 팀만 만들어지므로 power배열의 끝에서부터 안쪽으로 상대팀과의 능력 차 구해주면 됨
• result에 능력 차이 값을 담고, 마지막에 min(result)로 정답 출력

import sys; input = sys.stdin.readline
from itertools import combinations

result = []
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

nums = [i for i in range(0,n)]

p = list(combinations(nums, int(n/2)))
power = [0] * len(p)
for i in range(len(p)):
    p_list = list(combinations(p[i], 2))
    for j in p_list:
        x, y = j
        power[i] += graph[x][y] + graph[y][x]

for i in range(int(len(power)/2)):
    j = len(power)-i-1
    result.append(abs(power[i]-power[j]))

print(min(result))

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

• 뒤에서부터  DP
• 맨 마지막 스케줄은 하루만에 끝날 때만 profit 더해주고 아니면 0으로 초기화.
• 그 앞의 스케줄은 기간 안에 끝낼 수 있을 때 먼저  dp배열 안에 해당 profit 넣어주고
• 앞으로의 스케줄 중 도달할 수 있는 곳부터 max값 체크해서 또 더해줌.
• 처음엔 앞에서부터 DP했는데, 이 경우 마지막 테스트 케이스를 통과할 수 없음.
• 1일 다음에 6,7일을 선택하는 것(profit=80)보다 8일을 선택하는게(profit=90) 값이 더 크기 때문.

import sys
input = sys.stdin.readline

n = int(input())
schedule = []
dp = [0] * n

for _ in range(n):
    schedule.append(list(map(int, input().split())))

for i in range(n-1, -1, -1):
    day, profit = schedule[i]

    if i == n-1:
        if day == 1:
            dp[i] = profit
        continue

    if day + i <= n:
        dp[i] += profit
        if day + i < n:
            dp[i] += max(dp[day+i:])

print(max(dp))

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

• 얼핏 봤을 땐 BFS 문제라고 생각함
• 하지만 DP 문제였음..
• BFS / DP 어떻게 구분..?

import sys
input = sys.stdin.readline

n, m = map(int, input().strip().split())
graph = [list(map(int, input().strip().split())) for i in range(n)]

# 첫 번째 행 업데이트
# 이미 지나온 길은 다시 못가므로 오른쪽으로 갈 수 밖에 없음
for i in range(1, m):
    graph[0][i] += graph[0][i-1]

# 나머지 행 업데이트
for i in range(1, n):
    # 아래로 내려올 때의 값들
    startLeft = [graph[i][j]+graph[i-1][j] for j in range(m)]
    startRight = [graph[i][j]+graph[i-1][j] for j in range(m)]

    # ->
    # 아래로 내려온 값과 왼쪽으로 가는 값 비교해서 더 큰 값 저장
    for j in range(1,m):
        startLeft[j] = max(startLeft[j], startLeft[j-1]+graph[i][j])

    # <-
    for j in range(m-2, -1, -1):
        startRight[j] = max(startRight[j], startRight[j+1]+graph[i][j])

    for j in range(m):
        graph[i][j] = max(startLeft[j], startRight[j])


print(graph[-1][-1])

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

내 풀이

from collections import Counter
def solution(N, stages):
    answer = []
    rates = {x : 0 for x in range(1,N+2)}
    rates.update(dict(Counter(stages)))
    
    total = len(stages)
    
    for k in range(1,N+2):
        v = rates[k]
        if v != 0:
            rates[k] = v/total
        total -= v
    
    rates = sorted(rates.items(), key = lambda x : x[1], reverse=True)
    
    for k, v in rates:
        if k != N+1:
            answer.append(k)
    
    return answer

다른 사람 풀이

def solution(N, stages):
    result = {}
    denominator = len(stages)
    for stage in range(1, N+1):
        if denominator != 0:
            count = stages.count(stage)
            result[stage] = count / denominator
            denominator -= count
        else:
            result[stage] = 0
    return sorted(result, key=lambda x : result[x], reverse=True)

• Counter 대신에 count를 사용해서 1부터 N까지의 갯수만 구함 : 나와 달리 N+1은 무시
• sorted 할 때 인자값으로 result dict 자체를 넣으면 key만 담긴 정렬된 배열 return : 나는 rates.items()를 이용했더니 반환값이 (k, v) set으로 이뤄진 배열이었음

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

• 10, 3, 7, 4, 12, 2
• buildings를 차례대로 돈다
• stack이 비어있으니까 일단 10은 stack에 바로 append
• 3은 10보다 작으니까 stack에 append하고 answer += 1
• 7은 10에서는 볼 수 있고 3에서는 못 보니까 7보다 작은 3은 pop하고 7 append : answer += 1
• 4는 10과 7이 모두 볼 수 있으니까 append : answer += 2
• 12는 stack에 있는 10,7,4 모두가 볼 수 없으므로 stack은 계속 pop
• 2는 12가 볼 수 있으므로 stack에 append : answer += 1

import sys
r = sys.stdin.readline
n = int(r())

answer = 0
stk = []
buildings = []

for _ in range(n):
    buildings.append(int(r()))

for b in buildings:
    while stk and stk[-1]<=b:
        stk.pop()
    stk.append(b)
    answer += len(stk)-1

print(answer)

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

현차 코테 문제 중에 있었던 유형 같다

• stack에 [탑의 높이, index]를 2차원 배열 형태로 저장
• 높이를 비교하면서 가장 높은 값이 stack에 남을 수 있도록 업데이트
• 가장 가까이 위치한 탑이 출력되야 하므로 for문 돌릴 때마다 일단 stack에 append해줘야 함

import sys
r = sys.stdin.readline

n = int(r())
t_list = list(map(int, r().split()))
answer = []
stk = []

for i in range(n):
    h = t_list[i]
    while stk:
        if stk[-1][0] > h:
            answer.append(stk[-1][1]+1)
            break
        else:
            stk.pop()
    if not stk:
        answer.append(0)
    stk.append([h, i])

print(*answer)