http://www.acmicpc.net/problem/1562 # 조건 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. # 접근 방법 dp와 비트마스킹을 통하여 풀어주었다. DP [마지막 자리의 숫자] [비트 마스킹] 비트 마스킹의 경우 현재까지 사용된 숫자를 기록해준다. 2 4 5를 가지고 있다면 000011010..

http://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net # 조건 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열이 주어진다. 이 ..

http://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net # 조건 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자..

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)이 주어진다. 다음 두 줄에는 ..