2156번 포도주 시식회에서 가장 잔 많이 마시기ㅋㅋ

딴짓 좀 해서 40분 걸림ㅠ 이런 3번 연속 선택은 안된다 류를 저번에 계단 점수 내기 문제에서 풀어봐서 바로 풀 수 있었음. [[14일차 백준#^46f237]] 근데 역시 인덱스에러가 났는데 이게 dp[3] 까지 디폴트로 접근하다보니까 그때도 이런 에러 났던거같음.

import sys
sinput = sys.stdin.readline

n = int(input())
wine = [int(sinput()) for _ in range(n)]
dp = [0] * n
dp[0] = wine[0]
if n >= 2:
    dp[1] = dp[0] + wine[1]
if n >= 3:
    dp[2] = max(wine[0]+wine[1], wine[1]+wine[2], wine[0]+wine[2])

    for i in range(3, n):
        # dp[i]에서 내릴 수 있는 결정은 3 가지 
        # 나(wine[i])를 선택하는 경우 2가지와, 선택하지 않는 경우 1가지
        dp[i] = max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i], dp[i-1]) 

print(dp[n-1])

이렇게 푼 사람도 많고 아니면 dp[i] 를 case 3가지를 가지는 리스트로 즉 dp를 이차원 리스트로 선언해서 맨 마지막에 max(dp[n-1]) 하는 방법으로 많이 하심.근데 이건 10배 느림.

10844 계단수(인접한 모든 자리의 차이가 1인 수) 찾기

1시간 30분 걸림. 쉬울 줄 알았는데 정답률 30퍼인 이유가 있군… dfs로 풀면 시간초과 날 것 같아서 100자리수면 10^100 이니까;; dp로 해야한다고 생각해서 귀납적으로 3자리수 까지 해보면서 규칙(수식)을 찾아내려 했으나 힘들었음. 그러다가 끝자리수가 몇개인지만 카운트하면 되겠다 생각해서 dictionary로 품. 그리고 바로 풀릴 줄 알았으나 틀림. 문제가 있었음. 처음에 tempDict를 사용 하지 않아서 같은 자리수임에도(겉 포문이 1번 도는 와중) 만약 0이 1의 카운트를 증가시키면 1이 증가한 카운트로 나머지 0과 3에 영향을 미치는 것을 발견함. tempDict를 사용하여 영향을 미치지 않게했고, tempDict의 초기값을 고민 하는 와중에 (처음엔 cntDict를 그냥 카피함;; 이러니까 수가 너무 커짐) 왜 2가 17이 아니고 20 몇이 나올까 고민하다보니까 1로 끝나는 수에 0과 2를 붙이면 1로 끝나는 수는 사라지니까 1의 개수를 유지한채 거기에 2와 0의 카운트를 더해주는게 아니라 각 수의 초기값은 0이어야했음 ㄷㄷ 결론적으로 생각할게 많고 함정이 있어 어려웠다.

n = int(input())
divide = 1000000000

cntDict = {i : 1 for i in range(10)}
cntDict[0] = 0
# 계단수 뒤에 끝자리와 -1, +1 차이 나는 수를 붙이면 그 수도 계단수.
# 0이랑 9로 끝나는 수는 예외 처리.
for _ in range(n-1):
    tempDict = {i : 0 for i in range(10)}

    for digit, cnt in cntDict.items():
        if digit - 1 >= 0:
            tempDict[digit-1] += cnt
        if digit + 1 <= 9:
            tempDict[digit+1] += cnt

    cntDict = tempDict

print(sum(cntDict.values()) % divide)

모든 사람들이 dp 방식으로 품. 내가 좀 이상하게 풀었구나ㅋㅋ dp가 맞는게 이전의 값이 다음 값에 영향을 주니까. 근데 나는 dp[i]를 i 자리수의 1차원으로 선언해서 계속 해맸던 것 같다. 하지만 모두 아이디어는 같은 곳에서 출발함.

N = int(input())

dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
    dp[1][i] = 1

MOD = 1000000000

for i in range(2, N+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 

print(sum(dp[N]) % MOD)

즉 2차원 리스트로 dp를 선언하고 각 자리수는 초기값이 0이니까 자리수가 올라가면 무베이스에서 시작하니까 tempDict 같은 것도 필요없군~ 그리고 divide 말고 module의 의미를 가진 MOD를 나도 앞으로 쓰자 이게 더 멋져~

14888번 연산자 끼워넣어 최대,최소값 구하기

1시간 30분 걸림. 논리로 풀어볼까 했지만 너무 어지러워서 dfs로 모든 경우의 수를 다 해보는 수 밖에 없다고 생각함. 다행히 n이 최대 11이었기 때문에 가능했음… n이 11이면 연산자는 10개니까 O(10! / (op[0]! x op[1]! x op[2]! x op[3]]) 10^8 안으로 들어와서 다행히 풀 수 있었다.

import sys
sys.setrecursionlimit(10**8)

n = int(input())
a = list(map(int, input().split()))
op = list(map(int, input().split()))
ansMin = float('inf')
ansMax = -float('inf')

def calculator(i, result, cnt):
    global ansMin, ansMax
    
    if i == n:
        ansMax = max(ansMax, result)
        ansMin = min(ansMin, result)
        return

    if cnt[0] != 0:
        cnt[0] -= 1
        calculator(i+1, result+a[i], cnt[:])
        cnt[0] += 1

    if cnt[1] != 0:
        cnt[1] -= 1
        calculator(i+1, result-a[i], cnt[:])
        cnt[1] += 1

    if cnt[2] != 0:
        cnt[2] -= 1
        calculator(i+1, result*a[i], cnt[:])
        cnt[2] += 1

    if cnt[3] != 0:
        cnt[3] -= 1
        if result >= 0:
            calculator(i+1, result//a[i], cnt[:])
        else:
            calculator(i+1, -((-result)//a[i]), cnt[:])
        cnt[3] += 1

calculator(1, a[0], op[:])

print(ansMax)
print(ansMin)

음수 나눗셈이 파이썬이랑 c++ 동작이 다르다는 걸 깨달은 문제. -1 % 3 하면 파이썬은 0이 아닌 -1이 나오기 때문에 저런 처리가 필요했음. 그리고 완벽한 줄 알고 제출 했는데 틀렸음. 혹시나 싶어 2 5 6 0 1 0 0 를 넣어보니 -1, -1 이 출력되지 않고 0, -1이 출력됨. 내가 ansMax 초기화를 0으로 해서 그런거였음ㅠ_ㅠ 고치니까 통과~ 휴… 그리고 리스트를 파라미터를 주고 받을때 공부좀 함... 보니까 슬라이씽이 최고다. 슬라이씽하게 되면 id가 랜덤으로 따져서 deepcopy 처럼 되기 때문에 꼭 기억하자~

def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)

이 방식이 더 이쁘다 ㅎㅎ