본문 바로가기
728x90

동적

[백준알고리즘] 11052번: 카드 구매하기 -Python [백준알고리즘] 11052번: 카드 구매하기 -Python https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 반드시 N개를 구매하면서 가장 비싸게 주고 사는 경우를 구해야 한다. 입력받은 값으로부터 누적해 나가면서 i개를 살 때 가장 비싸게 주는 값을 구해나갔다. 최종적으로 N개를 구매할 때 가장 비싸게 사는 방법을 계산했다. 각 인덱스 마다 값을 구하기 위해서 다음과 같이 생각했다. 1개를 살 때: 0 + 1 2개를 살 때: 0 + 2 1 + 1 3개.. 더보기
[백준알고리즘] 2011번: 암호코드 -Python [백준알고리즘] 2011번: 암호코드 -Python https://www.acmicpc.net/problem/2011 1 101010 ->1 처음에 푼 코드에서 몇 자리 이어지냐에 따라서 cnt를 세는데 cnt[i] = cnt[i-1] + cnt[i-2]를 구하기 위해서 길이가 3인 리스트를 이용했다. import sys mod = 1000000 N = [0] N += list(map(int, list(sys.stdin.readline().strip()))) cnt = [1, 1, 1] res = 1 for idx in range(1, len(N)): if N[idx] == 0 and N[idx-1] != 1 and N[idx-1] != 2: res = 0 break elif N[idx] == 0: re.. 더보기
[백준알고리즘] 2225번: 합분해 -Python [백준알고리즘] 2225번: 합분해 -Python https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제는 조금 오래 걸렸다. 한시간이 안되게 걸리긴 했지만 그래도 DP인 것을 알고 풀어서 그나마 나았지.. 몰랐으면 고생을 조금 더 했을 것 같다. 풀이를 적었는데 앞부분은 너무 두서없는 것도 같고 뒤에 갈수록 이해는 될 것 같기도 하고.. 이번 문제는 0부터 N까지 K개의 수를 더해서 N을 만드는 문제이다. 여기서 중요한 것은 강조한 것처럼 "0부터"라는 것이다. 예시에서 주어진 문제를 살펴보면 쉽게 이해할 수 있다. 예제 입력으로 20 2 가 주어졌는데, 2개의 수.. 더보기
[백준알고리즘] 9461번: 파도반 수열 -Python [백준알고리즘] 9461번: 파도반 수열 -Python https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하 www.acmicpc.net 초기에 5번째 삼각형까지는 길이를 직접 넣어주었다. 그리고 그림에서의 규칙을 .. 더보기
[백준알고리즘] 2133번: 타일 채우기 -Python [백준알고리즘] 2133번: 타일 채우기 -Python https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net 이번 문제는 집중력이 부족하기도 했고 어렵기도 했다. ㅠㅠㅠㅠㅠ 다 풀고 보니까 너무 간단해보이는데... 우선은 짝수일 때만 채울 수 있다. 홀수에서는 채울 수 있는 방법이 없고, 무조건 0을 출력하게 된다. 그리고 2칸일 때는 3가지의 경우가 존재한.. 더보기
[백준알고리즘] 1699번: 제곱수의 합 -Python [백준알고리즘] 1699번: 제곱수의 합 -Python https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 이번 문제는 Python3로 통과하지 못하고 PyPy3로 통과할 수 있었다. P.. 더보기
[백준알고리즘] 2579번: 계단 오르기 -C, Python [백준알고리즘] 2579번: 계단 오르기 -C, Python https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 이전에 풀었던 문제인데 새로 풀어보았다. 이전에 C로 풀었었는데 포스팅을 안 해서 같이 올리려.. 더보기
[백준알고리즘] 1309번: 동물원 -Python [백준알고리즘] 1309번: 동물원 -Python https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이 문제는 세가지 경우로 나눠서 생각하면 된다. 현재 2xN크기의 우리가 존재한다고 했을 때 2x1부터 차례대로 늘려가며 생각을 할 것이다. i번째 행을 추가할 때를 생각해보겠다. i번째 행을 추가할 때 i번째 행에 사자를 배치할 수 있는 경우의 수는 3가지이다. 왼쪽과 오른쪽 어느 곳에도 배치하지 않는 것, 왼쪽에 배치하는 것, 오른쪽에 배치하는 것. 이 3가지를 기준으로 생각할 것이다. 1. i번째 행에 사자 배치 안 하기 i번째 행에 사자를 배치 안 하는 경우는 i-1번째에 .. 더보기
728x90

티스토리툴바