본문 바로가기

백준13

[백준] 1041: 주사위 파이썬 리뷰 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. 처음 보는 유형이라 굉장히 복잡하게 느껴졌습니다. 하지만 주사위 면이 보이는 경우에 따라 나눠 생각하면 3가지 밖에 되지 않기 때문에 생각한 거 보다 간단했습니다. (M 면이 보이는 주사위의 수) X (M 면의 최소합) 으로 3가지 경우를 모두 구해 더해주면 됩니다. M 면의 최소합을 구하는 것이 굉장히 생소했습니다. 주사위 특성상 마주보는 면을 제외하고 모든 면이 인접해있다. 따라서 A,B,C,D,E,.. 2021. 2. 19.
[백준] 14501: 퇴사 파이썬 리뷰 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이는 해당 블로그를 참고했습니다. dp 계산을 N부터 시작하는 방법을 사용해야 했습니다. 뒤에서 부터 계산을 해보면 다른 동적 계획법과 풀이 방법은 비슷합니다. 파이썬 코드 import sys readline = sys.stdin.readline N = int(readline()) T, P = [], [] for _ in range(N): t, p = map(int, readline().split()) T.append(t) P.append(p) d = [0] * (N+1) for i in range(N - 1, -1, -1): # i일에 상담을 하는 것이 퇴사일을 넘기면 상담을 하지 않음 if i .. 2021. 2. 14.
[백준] 2133: 타일 채우기 파이썬 리뷰 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 풀이는 블로그 1, 블로그 2 를 참고했습니다. d(i-4) * 2 + ... + d(0) * 2 부분이 이해하기 힘들었습니다. 점화식은 역시 그려봐야 이해가 됩니다... 파이썬 코드 N = int(input()) d = [0]*31 d[0] = 1 for i in range(2, N+1, 2): d[i] = d[i-2] * 3 for j in range(0, i-2, 2): d[i] += d[j] * 2 print(d[N]) 2021. 2. 13.
[백준] 10844: 쉬운 계단 수 파이썬 리뷰 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 방법은 해당 블로그를 참조하자 dp 테이블을 각 자리수 마다 한줄 씩 2차원 배열로 설정한다. (행 : 자릿 수, 열 : 0~9) 테이블에는 해당 숫자가 맨 앞에 있을 때 가능한 경우의 수를 저장한다. 예를 들어, dp[2][1]에는 백의 자리 숫자가 1인 경우의 수가 저장돼있다. 101, 121, 123 dp[2][1]을 저장했을 때를 생각해보자, dp[1][0]과 dp[1][2]를 더한 값이 dp[2][1]에 저장된다. 맨 앞의 숫자가 1이라면 그 뒤에 올 수 있는 숫자는 당연히 0 또는 2이다. 2이 맨 앞에 있을 때 경우의 수는 dp[1][2]에 저장 돼 있다. 0.. 2021. 2. 4.

티스토리툴바