본문 바로가기
728x90

동적

[백준알고리즘] 2156번: 포도주 시식 -Python [백준알고리즘] 2156번: 포도주 시식 -Python https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 이전에 풀었던 문제인데 다시 풀어보게 되었다. 동적 계획법 문제이다. 존재하는.. 더보기
[백준알고리즘] 9465번: 스티커 -Python [백준알고리즘] 9465번: 스티커 -Python https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 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 쉬운 계단 수 문제와 유사하다. 여기서는.. 더보기
[백준알고리즘] 10844번: 쉬운 계단 수 -Python [백준알고리즘] 10844번: 쉬운 계단 수 -Python https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이번 문제도 DP 문제이다. 처음에 생각했던 것과 코드로 작성한 것이 쪼끔 개념이 다르긴 한데, 전체적으로는 같다. 우선 계단 수에서 한 자릿수에 대하여 리스트에 저장해 놓았다. 그리고 리스트에 저장되어 있는 값은 현재 해당 인덱스가 마지막 수, 즉 1의 자리 수일 때 가능한 수의 개수이다. 음.. 한 자릿수일 때가 아닌 두 자리 수일 때를 풀이해보면 이해가 될 것 같다. 한 자리가 늘어나게 될 때 1의 자리 수가 0이 되기 위해서는 앞자리가 1일 수밖.. 더보기
[백준알고리즘] 9095번: 1, 2, 3 더하기 -Python [백준알고리즘] 9095번: 1, 2, 3 더하기 -Python https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 동적 계획법으로 문제를 해결했다. 한 번 DP문제를 풀기 시작.. 더보기
[백준알고리즘] 11727번: 2xN 타일링 2 -Python [백준알고리즘] 11727번: 2xN 타일링 2 -Python https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net 이전과 똑같이 두가지 방법으로 풀었다. 이전 문제인 11726번 문제 풀이와 거의 같다. 아무튼 이전 글을 거의 복사해서 써야겠다. ㅎㅎ 이번 문제에서는 첫 번째 방법의 설명이 조금 난해한 것 같아 두 번째 방법을 보고 첫 번째 방법을 봐도 괜찮을 것 같고.. 그렇다... 두 번째 방법을 보면 첫 번째 방법을 안 볼 것 같지만 말이다. 첫 번째 방법. 우선 첫 번째 방법은 Combination을 사용했다. N을 1부터 늘려.. 더보기
[백준알고리즘] 11726번: 2xN 타일링 -Python [백준알고리즘] 11726번: 2xN 타일링 -Python https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 우선 이 문제를 풀 때 두 가지 방법으로 해결했다. 첫 번째 방법은 직접 푼 방법이고, 두 번째 방법은 문제를 해결하고 다른 사람들의 코드를 보니 다 똑같길래 이유를 이해하고 따라한 코드다. 두 번째 방법이 훨씬 쉽다. 첫 번째 방법. 우선 첫 번째 방법은 Combination을 사용했다. 그림까지 하기는 너무 오래 걸릴 것 같다.. N을 1부터 늘려가며 생각.. 더보기
728x90

티스토리툴바