본문 바로가기
728x90

점화식

[백준알고리즘] 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번째 삼각형까지는 길이를 직접 넣어주었다. 그리고 그림에서의 규칙을 .. 더보기
[백준알고리즘] 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번째에 .. 더보기
[백준알고리즘] 2156번: 포도주 시식 -Python [백준알고리즘] 2156번: 포도주 시식 -Python https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 이전에 풀었던 문제인데 다시 풀어보게 되었다. 동적 계획법 문제이다. 존재하는.. 더보기
[백준알고리즘] 2193번: 이친수 -Python [백준알고리즘] 2193번: 이친수 -Python https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 이진수에서 0으로 시작하지 않는 N자리 수 중에서 1이 두 번 연속으로 등장하지 않는 수.. 더보기
[백준알고리즘] 11057번: 오르막 수 -Python [백준알고리즘] 11057번: 오르막 수 -Python https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다. www.acmicpc.net 수의 자릿수가 주어지면 인접한 수가 같거나 오름차 순을 만족하는 수의 갯수를 구해야 한다. 이 문제는 동적 계획법으로 해결이 가능하다. 이전에 풀었떤 10844 쉬운 계단 수 문제와 유사하다. 여기서는.. 더보기
728x90

티스토리툴바