Dalin's Archive

문제로 가기 접근 🌰🍂 DP로 풀었다. 어떤 색으로 집을 칠할지, 몇 번째 집인지를 담은 2차원 리스트를 만들었다. 1번 집은 그냥 칠하면 된다. 그 이후 집들은 그 이전 집 색깔과 겹치지 않게 최소 비용으로 칠했다. 예를 들어, 현재 집을 빨강으로 칠할 때의 최소 비용을 구해야 하는 경우를 생각해보자. 그 이전 집이 초록일 때, 파랑일 때 최소 비용 중 싼 것을 택하고, 현재 집을 빨강으로 칠하는 비용을 더해서 dp 테이블을 채웠다. 코드 👩‍💻 import sys input = sys.stdin.readline N = int(input()) house_color_costs = list(list(map(int, input().split())) for _ in range(N)) dp = [[0] * 3 ..

문제로 가기! 헐 ㅠㅠㅠㅠ 내가 이 문제를 풀다니ㅠㅠㅠ 나는 DP 문제는 식 생각하는 게 어려워서 좀 자신이 없다... 그래서 이 문제를 봤을 때도 '내가 풀 수 있을까?'하면서 봤다. 그래도 나름 종이에 끄적끄적하다보니 이런 식으로 DP 풀면 되겠다는 생각이 났다. 그리고 하나 하나 구현했더니 맞았습니다 !! 가 나왔다 ㅠㅠㅠ 코드를 쓰기 전에 미리 생각하는 게 중요한 것을 다시 한번 느꼈다 ! 접근 일단 천사 다리부터 시작하는 경우, 악마 다리부터 시작하는 경우를 나눠서 생각했다. 악마 다리에서 시작하는 예시를 가지고 설명하겠다. 일단 dp 테이블을 다 0으로 세팅하고 시작한다. dp 테이블은 3차원 리스트로 만들었다. 무슨 다리인지, 각 다리에서 몇 번째 돌인지, 마법 두루마리에서 몇번째 글자인지를..

백준 문제 보러 가기~! 코드😎 n = int(input()) dy = [0]*(n+1) if n == 3: print(n) else: dy[1] = 1 dy[2] = 2 for i in range(3,n+1): dy[i] = dy[i-1]+dy[i-2] print(dy[n]%10007)설명😊 다이나믹 프로그래밍!! 일단 n이 1이라면, 당연히 답은 1이다. 세로로만 세울 수 있다. n이 2라면 답은 2이다. 세로로 두개 혹은, 가로로 두개가 가능하다. n이 3이라면 두 가지 경우로 나눌 수 있다. 맨 끝 부분에서, 세로로 하나인 경우, 그러면 그 안쪽부분은 2개가 있다. 그럴 때 안쪽 2개를 배치하는 방법은 n=2일 때 경우의 수와 같다. 맨 끝 부분에서 가로로 두개를 둘 경우, 안쪽에는 하나만 남았다..

문제 보러 가기!! TMI로 시작하는 서론 이 문제는 전에 풀었던 포도주 시식 문제와 비슷한 식으로 풀었다..! 그 문제는 어떻게 풀어야 할지 잘 모르겠어서, 친구에게 물어봐서 풀었다. 포도주 시식 백준 문제 보러가기~ 벨로그에 올린 문제풀이 보러가기! 그러다 이를 활용해서 숫자카드를 혼자서 푸니 너무 뿌듯하고 기분이 좋아서 벨로그에 글을 쓴다 ㅎㅎ 😍 아이디어, 설명 2차원 리스트를 활용해서 풀었는데 말보다 그림이 더 이해가 잘 될 것 같아서, 그림을 올린다..! 숫자를 문자열로 받아서 인덱스로 하나 하나 본다. 2차원 리스트 dp의 열은 각각 인덱스의 숫자를 1자리로 표현할 때 경우의 수 누적, 이전 인덱스의 숫자와 해당 인덱스의 숫자를 2자리 카드로 표현할 때 경우의 수 누적을 의미한다. 행은 각각..

문제 보러 가기~! 아이디어 🌊 내가 전에 풀었던 DP들과는 다른 유형(?)인 것 같아서,,, 생각하다가 모르겠어서 친구에게 힌트를 얻었다.. 이런 점화식은 도대체 어떻게 생각해내는지 신기하다!! ㅠㅠ 코드 👩‍💻 n = int(input()) wines = [] for _ in range(n): wines.append(int(input())) wines.insert(0,0) drunk_wine = list([0]*(n+1) for _ in range(3)) # print(drunk_wine) for i in range(1, n+1): drunk_wine[0][i] = max(drunk_wine[0][i-1], drunk_wine[1][i-1], drunk_wine[2][i-1]) drunk_wine[1..

문제 보러 가기! 아이디어 🌼 처음에는 DFS로 코드를 짰다. 2, 10 정도는 금방 답이 나왔지만... N의 범위가 10의 6제곱... 10000 정도만 해도 시간이 오래 걸렸다. 또 지금 생각해보니, 최대 재귀 깊이를 초과할 수 있겠다는 생각도 든다..! 다시 짠 코드 ! 3가지 종류의 계산이 있는데, 가능한 계산을 하고, 그 중에 가장 횟수가 적은 것을 dp에 넣는다! 코드 📝 N = int(input()) dp = [0, 0, 1, 1] + [0] * N # 0, 1번 인덱스는 편하게 쓰려고 추가. 2에서 1로 가는 최소 연산 수는 1, 3에서 1로 가는 최소 연산 수는 1개. for i in range(4, N + 1): # N을 구해야 하니까 그때까지 보기 if i % 6 == 0: # i가 ..