2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net DP문제인데, DP문제의 가장 중요한 점은 문제를 보고 DP를 떠올릴 수 있어야 하고 테이블링을 할 수 있어야 한다. 가장 먼저 떠오른 풀이는 백트래킹이다. n자리를 모두 체크해보고 이친 수인지 판단하는 방법인데, 2^n의 데이터를 검사해야 하므로 바로 패스했다. 또 바로 떠오르는 풀이가 없으니 일단 n=1부터 n을 증가시키면서 규칙을 찾아보았다. 다행히 n=3부터 n=1에서 구했던 부분을 써먹을 수 있었다. n을 계속 늘려가면서 6 정도까지 관찰해 ..

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 예제 9 ans : 55 문제를 처음 봤을 때 바로 dp로 풀어야겠다 생각한 건 아니고 완전 탐색으로 셀 수 있나 생각을 해 봤다. 타일을 완전 탐색으로 채우는 것 자체가 힘들어 보여서 일단 손으로 보드를 채워보면서 문제를 파악했다. 딱 정확히 이 사진의 흐름대로 2*3에서도 2*2와 2*1을 이용해서 채운 느낌이 들었고 2*4 블록을 채울 때 확신이 생겼다. 2*k 블럭을 예로 들자면, 세로로 긴 블록을 하나 먼저 세우면 나머지 k-1열 2*k-1 블록을 채우는 방법과 정확히 똑같다..

2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 9 3 1 3 3 3 2 2 2 1 1 ans : 1 1 1 3 3 3 2 2 2 빈도를 기준으로 정렬하되, 들어온 순서를 유지하면서 정렬해야 한다. 빈도만 기준이었다면 떠오르는 방법은 아래와 같다. 맵에 빈도를 key로 값을 value로 해서 삽입한다. pair vector에 빈도, 값으로 삽입을 한 뒤 빈도를 기준으로 sort를 한다. 두 방법에서 기존 입력의 순서를 유지할 방법을 생각해 봤는데, sort를 병합 정렬로 직접 구현하지 않는 이상 맵이나 벡터를 확장하는 방법이었다. 맵 2개 사용, 하나..

Merge Sort 먼저 구현부터 해보자. 재귀 형태로 구현했다. 함수 정의 void merge_sort(int start, int end) : start ~ end - 1까지 병합 정렬을 실행한다. base condition if(길이가 1) return; 재귀식 배열을 반으로 쪼개서 병합정렬을 한 후 merge 함수를 써서 병합하면 된다. merge 함수는 정렬된 두 배열을 병합하는 함수이다. 배열을 반으로 쪼개서 병합정렬을 한다는 건 귀납적 사고를 통해 재귀식을 구성했다고 생각하면 된다. 길이가 4인 배열을 병합정렬 할 수 있다고 가정하면 길이가 8인 배열은 길이가 4인 배열을 합치면 끝이다. 이런 느낌으로 구현해 보자. #include #include using namespace std; int ..

14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 예제 5 5 1 2 3 4 5 5 4 3 2 1 2 3 4 5 6 6 5 4 3 2 1 2 1 2 1 ans : 19 문제 분석부터 해보자. 테트로미노라는 블록을 보드에 넣는데, 블록이 들어가는 칸의 합이 가장 크게 되는 숫자를 찾으면 된다. 테트로미노는 총 5 종류고, 가장 먼저 떠오르는 방법은 모든 테트로미노를 하나하나 끼워 넣는 방법이다. 보드의 크기가 2500이고 블록 단 한 개만 넣으면 되므로 모든 테트로미노를 다 끼워보는 방법으로 구현해도 될 것 같다...

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 분석부터 해보자. N * M 크기 보드에 파란 구슬, 빨간 구슬이 하나씩 있고 상하좌우 기울여서 구슬이 구멍에 들어가는지 관찰하면 된다. 빨간색만 빠지면 성공이고 빨, 파 동시에 빠지거나 파란색만 빠지면 실패이다. 10번 이상 움직여도 실패이다. 문제를 보고 예제들을 한 번 훑어보면서 생각난 주의 사항은 다음과 같다. 공 하나가 구멍에 빠지는 경우를 주의하자. (예제 7) 움직일 때 두 공이 겹칠 수 없다. ..