http://www.acmicpc.net/problem/27210 27210번: 신을 모시는 사당 칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라. www.acmicpc.net # 조건 신을 모시는 사당에는 신을 조각한 돌상 N개가 일렬로 놓여 있다. 각 돌상은 왼쪽 또는 오른쪽을 바라보고 서있다. 창영이는 연속한 몇 개의 돌상에 금칠을 하여 궁극의 깨달음을 얻고자 한다. 궁극의 깨달음을 얻기 위해서는 가능한 한 많은 금색 돌상들이 같은 방향을 바라보아야 한다. 방향이 다른 돌상은 깨달음에 치명적이다. 깨달음의 양은 아래와 같이 정의된다. | (왼쪽을 바라보는 금색 돌상의 개수) - (오른쪽을 바라보는 금색 돌상의 개수) | ..

http://www.acmicpc.net/problem/23762 23762번: 배드민턴 복식 팀 만들기 (1, 4, 2, 3), (96, 99, 97, 98) 의 두 팀을 만들고 4번, 5번을 빼는 것이 실력 차를 최소로 만들 수 있다. www.acmicpc.net # 조건 고려대학교 배드민턴 동아리원들이 배드민턴을 치려고 한다. 모두가 동시에 재밌게 배드민턴을 치기 위해, 동아리원들의 각각의 실력을 고려하여 다음과 같이 복식 팀을 만들려고 한다. 배드민턴 복식은 2명이 짝을 지어 대결하기 때문에, 양쪽에서 총 4명이 한 팀을 이루어 게임을 진행한다. 또한 모든 사람의 배드민턴 실력을 자연수로 나타낼 수 있다. 이 때 각 팀의 (실력 최댓값) - (실력 최솟값) 을 그 팀의 실력차라 하자. 비슷한 실력..

http://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net # 조건 새 집의 크기는 N x N 격자판으로 나타낼 수 있고, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있고 r은 행의 번호, c는 열의 번호이며 행과 열의 번호는 1부터 시작한다. 파이프는 아래와 같은 형태이고 2칸을 차지한다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 빈 칸만 차지할 수 ..

http://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net # 조건 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 ..

http://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net # 조건 N줄에 0이상 9이하의 숫자가 세 개씩 적혀 있다. 첫 줄에서 시작하여 마지막 줄에서 끝나게 되는 놀이이다. 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 아래와 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어있는 수로만 이동할 수 있다. 별표는 현재 위치, 파란 동그라미가 내려갈 수 있는 위치 ..

http://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net # 조건 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매 스티커는 아래 그림과 같이 2행 n열로 배치 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져 사용 불가 점수의 합이 최대가 되도록 스티커를 붙여라 # 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 ..

http://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net # 조건 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제 예 ACAYKP와 CAPCAK의 LCS는 ACAK # 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져있으며, 최대 1000글자로 이루어져 있다. ..

http://www.acmicpc.net/problem/23083 23083번: 꿀벌 승연이 첫째 줄에 \(N\), \(M\)이 공백으로 구분되어 주어진다. 다음 줄에는 구멍 칸의 개수 \(K\)가 주어진다. 이어서 \(K\)개 줄에 구멍 칸의 정보 \(x_i\), \(y_i\)가 공백으로 구분되어 주어진다. 이는 \(i\)번째 www.acmicpc.net # 조건 승연이가 사는 벌집은 조금 특이한 구조로 되어있다. 벌집은 N행 M열의 격자로 이루어져 있고, 각 칸은 정육각형 모양 같은 행에 위치한 두 칸을 비교했을 때, 짝수번째 열의 칸은 홀수 번째 열의 칸보다 반 칸 아래에 위치 두 육각형 칸이 하나의 변을 공유하고 있다면 서로 인접하다. 벌집 내에서는 아래쪽, 오른쪽 위, 오른쪽 아래 칸으로만 이동..

http://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net # 조건 위 그림은 크기가 5인 정수 삼각형 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하여라 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능하다. 삼각형의 크기는 1 이상 500이하 # 접근 방법 DP를 이용하여 각 수에 누적합을 구해주고 가장 큰 수를 출력해주면 된다. 입력을 층마다 받기 때문에 2차원 리스트를 사용한다 ..