본문 바로가기

분류 전체보기

 (120)
[백준] 11052번 : 카드 구매하기 (Python) 문제 : https://www.acmicpc.net/problem/11052  카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 문제다. import sysinput = sys.stdin.readlineN = int(input())# 카드 값 얻기card = [0] + list(map(int, input().split()))# DP 테이블 생성for i in range(1, N+1): for j in range(1, i): card[i] = max(card[i], card[j] + card[i-j]) # 카드팩 N개를 구매할 때의 가격 중 큰 값을 설정print(card[-1])   [문제풀이] 이 문제는 규칙 찾기, 즉..
[백준] 11727번 : 2×n 타일링 2 (Python) 문제 : https://www.acmicpc.net/problem/11727  2×n 크기의 직사각형을 1×2, 2×1, 2×2 타일로 채우는 방법의 수를 구하는 문제다. import sysinput = sys.stdin.readlineN = int(input())DP = [0]*1001MOD = 10007# 초기값 세팅DP[1] = 1DP[2] = 3# DP 테이블 생성for i in range(3, 1001): DP[i] = (DP[i-1] + 2*DP[i-2])%MODprint(DP[N]%MOD)  [문제풀이] 이 문제는 규칙 찾기, 즉 다이나믹 프로그래밍을 이용해서 풀 수 있다.     이걸 정리해 점화식으로 나타내면 이렇게 된다.D[i] = D[i-1]+2*D[i-2] 이걸 이용해 바텀-업..
[백준] 11726번 : 2×n 타일링 (Python) 문제 : https://www.acmicpc.net/problem/11726 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제다. import sysinput = sys.stdin.readlineN = int(input())DP = [0]*1001MOD = 10007# 초기값 세팅DP[1] = 1DP[2] = 2# DP 테이블 생성for i in range(3, 1001): DP[i] = (DP[i-1] + DP[i-2])%MODprint(DP[N]%MOD)  [문제풀이]  이 문제는 규칙 찾기, 즉 다이나믹 프로그래밍을 이용해서 풀 수 있다.     이걸 정리해 점화식으로 나타내면 이렇게 된다. D[i] = D[i-1]+D[i-2] 이걸 이용해 바텀-업(Bottom-..
[백준] 1309번 : 동물원 (Python) 문제 : https://www.acmicpc.net/problem/1309  이 문제는 가로로도 세로로도 붙어있지 않게,2*N 배열에 사자를 배치하는 경우의 수를 구하는 문제다. import sysinput = sys.stdin.readlineN = int(input()) # 우리의 크기DP = [1]*(N+1)MOD = 9901# DP 채우기DP[1] = 3for n in range(2, N+1): DP[n] = (2*DP[n-1]+DP[n-2])%MOD# 답 출력print(DP[N]%MOD)   [문제풀이] n-1 경우의 수에 2를 곱하고, n-2 경우의 수를 더한 값이 현재 사자를 배치할 수 있는 경우의 수!
[백준] 1149번 : RGB거리 (Python) 문제 : https://www.acmicpc.net/problem/1149  이 문제는 N개의 집을 각각 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,양옆의 집과 색이 같지 않으면서 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램이다. n = int(input()) # 집의 수 입력 받기# 각 집의 색상에 대한 비용 입력 받기costs = []for _ in range(n): costs.append(list(map(int, input().split())))# 각 집에서 최소 비용을 누적으로 계산for i in range(1, n): costs[i][0] += min(costs[i-1][1], costs[i-1][2]) costs[i][1] += min(costs[i-1][0], ..
[백준] 1932번 : 정수 삼각형 (Python) 문제 : https://www.acmicpc.net/problem/1932 이 문제는 위 사진과 같이 크기가 N인 정수 삼각형을 입력받아,맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램이다.  import sysinput = sys.stdin.readlineN = int(input()) # 삼각형의 크기A = []# 정수 삼각형 입력받기for i in range(N): arr = list(map(int, input().split())) A.append(arr)# 합배열 삼각형 만들기for i in range(1, N): A[i][0] += A[i-1][0] # 왼쪽 끝값 부모값 더하기 ..
[백준] 9095번 : 1, 2, 3 더하기 (Python) 문제 : https://www.acmicpc.net/problem/9095   이 문제는 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제다.  import sysinput = sys.stdin.readlineT = int(input()) # 테스트 케이스의 개수answer = [0]*(11) # 정답 리스트answer[:4] = [0, 1, 2, 4] # 초기 정답 저장# 정답 리스트 생성for i in range(4, 11): answer[i] = answer[i-1]+answer[i-2]+answer[i-3] # 다음 정답을 생성해 저장# 정답 구for N in range(T): N = int(input()) # 값을 구할 N 입력받기 print(answer[N])..
[백준] 1003번 : 피보나치 함수 (Python) 문제 : https://www.acmicpc.net/problem/1003   이 문제는 재귀함수로 피보나치 수열을 구할 때,fibonacci(0), fibonacci(1)이 호출되는 개수를 구하는 문제다.  import sysinput = sys.stdin.readlineT = int(input()) # 테스트 케이스의 개수answer = [0]*(41) # 정답 리스트answer[0] = [1, 0]answer[1] = [0, 1]# 정답 리스트 생성for i in range(2, 41): answer[i] = ([answer[i-1][1], sum(answer[i-1])]) # 다음 정답을 생성해 저장# 문제 입력 & 정답 구하기for _ in range(T): N = int(input(..

티스토리툴바