GOD동하님의 블로그

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1361&sca=5040 JUNGOL | 자리 배치 > 문제은행 어떤 극장의 자리는 한 줄로 배치되어 있고 자리번호는 왼쪽부터 1에서 N까지 차례대로 매겨져 있다. 이 N개의 자리 중에서 N-1개의 자리는 지정석으로 모두 판매하고, 어떤 한 자리만 자유석으로 비워둔다. 지정석 표를 산 사람들은 아래 규칙에 따라서만 앉을 수 있다. 규칙) 사람들은 구입한 지정석 표에 적힌 번호의 자리에 앉든지, 그 자리의 바로 왼쪽이나 오른쪽의 인접한 자리에 앉든지, 또는 자유석에 앉을 수 있다. 예를 들어 설명해보자. 4개의 자리가 www.jungol.co.kr 자유석을 기준으로 왼쪽 오른쪽으로 나누는 것이 포인트 ..

https://koitp.org/problem/IOI_1999_FLOWER/read/ Korea Olympiad in Informatics Training Program 문제 꽃집에서는 꽃을 꽃병에 꽂아 진열한다. F개의 서로 다른 꽃이 있고, V개의 꽃병들이 일렬로 있다. 꽃병들은 움직일 수 없고, 왼쪽에서부터 순서대로 1, 2, ..., V번까지 번호가 매겨져있다. 또한, 꽃은 1, 2, ..., F번까지 번호가 매겨져있다. 하나의 꽃병에는 하나의 꽃만 꽂을 수 있는데, 모든 꽃은 자신보다 큰 번호의 꽃보다 왼쪽에 있는 꽃병에 꽂아야 한다. 어떤 꽃을 어떤 꽃병에 꽂느냐에 따라 아름다움의 정도가 다르다. 이 아름다움의 koitp.org 이것도 전형적인 DP 문제.. (전형적인 DP라고 하면 부분문제 ..

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 문제를 푼다 사실 조건이 크지 않아 전체 탐색을 해도 상관 없지만 이런 문제로 DP 연습을 하기 딱 좋다..

RGB 거리 알고리즘 문제 Dynamic Programming을 연습하기에는 아주 전형적인 문제라고 생각한다. 풀이1 : 하향식 DP (Top-Down 재귀) 1. 큰 문제를 작은 문제로 분류 2. 최소 단위의 답을 해결하며 병합 풀이2 : 상향식 DP (Bottom-Up 반복문) 1. 작은 문제를 먼저 해결 2. 먼저 푼 문제의 답을 이용해 큰 문제를 해결 설명 : TODO 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475/** * RGB 거리 (문제번호 : 1149) * * @category Dyna..