작심 24/7

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net O(NlogN) LIS 알고리즘으로 풀어야 하는 문제이다. arr 배열엔 입력 값을 저장한다. tmp 배열의 인덱스는 수열의 길이를 나타내고 각 값은 현재 길이를 가진 수열의 마지막 원소 중 가장 작은 값의 위치를 저장한다. dp 배열엔 각 인덱스가 연결하고 있는 인덱스를 저장한다. 변수 len엔 지금까지 가장 긴 수열의 길이를 저장한다. 계산이 모두 끝나면 tmp[len]이 LIS의 마지막 원소의 위치를 가리키고 있으므로 dp[tm..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 기본적으로 DP로 길이만 저장하는 LIS를 구하는 방법에서 조금 변화를 주어 arr 배열엔 입력 값을 저장하고 len 배열엔 길이를 저장하고 dp 배열엔 현재 위치까지에서 가장 긴 수열을 가진 위치를 저장하였다. 그러고 출력할 땐 수열의 길이가 가장 길었던 위치부터 재귀 호출하여 그 수열의 처음까지 들어간 다음 출력하면서 빠져나왔다. #include using namespace st..

11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net ABCD를 계산하는 방법은 A(BCD), (AB)(CD), (ABC)D 세 가지로 나눌 수 있고 이 중에서의 최솟값이 ABCD의 값이 된다. A(BCD)에서 BCD는 B(CD), (BC)D 두 가지로 나눌 수 있고 이 중에서의 최솟값이 BCD의 값이 된다. (AB)(CD), (ABC)D도 분해하여 구한 최솟값을 저장하면 ABCD의 최솟값을 구할 수 있다. 이 과정을 표로 나타내 보면 ABCD를 구하기 위해선 A와 BCD, AB와 CD, ABC와 D를..

17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 궁수 3명을 배치시키는 경우는 M개 중 3개를 순서 상관없이 뽑는 조합으로 구하면 된다. 궁수가 (5, 2)에 있을 때 공격할 수 있는 위치에 따른 거리들을 표시해 보았다. 궁수가 공격할 수 있는 거리는 궁수 위치에서부터 좌, 상, 우 방향으로 BFS 했을 때의 깊이와 같다는 것을 알 수 있다. 공격할 수 있는 적은 거리가 D 이하인 적 중에서 가장 가까운 적이고 그런 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격해야 하므로 깊이 1부터 탐색해야 하고 방향은 왼쪽, 위쪽..

17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. 가로 2. 세로 3. 대각선 현재 위치는 항상 0번이고 가로일 땐 1, 3번 세로일 땐 2, 3번 대각선일 땐 1, 2, 3번으로 이동할 수 있다. 이 패턴을 이용해 이전에 어느 방향이었는지와 현재 위치를 넘겨주며 재귀 호출로 완전 탐색을 구현하면 된다. #include using namespace std; int N, d, res; int arr[17][17], dx[3] = { 0, 1, 1 }, dy[3] = { 1, 0, 1 ..

16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 1. 괄호로 묶지 않는 경우 이전까지의 값 OP 숫자 = res a[idx] a[idx+1] 2. 괄호로 묶는 경우 이전까지의 값 OP (숫자 OP 숫자) = res a[idx] (a[idx+1] a[idx+2] a[idx+3]) 재귀 호출을 이용해 수식의 처음부터 끝까지 돌면서 1번 경우는 무조건 계산하고 2번 경우는 뒤에 남은 수식이 괄호를 추가할 수 있을 만큼 남아있는 경우에만 계산한다. #include #include #include #in..

17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 주사위를 던질 때마다 선택할 수 있는 말은 4가지이고 주사위는 10번 던지므로 말을 이동하는 총 경우의 수는 4^10가지가 된다. (중복 순열) 게임판에서 말이 어떤 파란색 칸으로 이동하는지에 따라 경로가 달라진다. 1. 파란색 칸을 한 번도 밟지 않는 경우 (Default) 2. 1번 경로로 가다가 첫 번째 파란색 칸을 밟는 경우 3. 1번 경로로 가다가 두 번째 파란색 칸을 밟는 경우 4. 1번 경로로 가다가 세 번째 파란색 칸을 밟는 경우 이 네 가지 경우에 따른 경로를 이차원 배열 board에 저장해준다. 말을 이동시킬 때 같은 칸에 두 개 이상의 말이 있으면 안 되므로 A 말을 이..

17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 이차원 배열 arr[i][j]에서 i는 원판의 번호, j는 12시부터 시계 방향으로 돌아는 형태로 간주하였다. 1. 시계 방향이나 반시계 방향으로 K칸 회전시키는데 만약 M이 4인 원판이면 4칸 회전시키면 처음 상태로 돌아온다. M이 6인 원판은 6칸 회전 시키면 처음 상태로 돌아온다. 그러므로 불필요하게 원판을 여러 번 돌리는 경우를 막기 위해서 원판을 K%M칸 만큼 회전시키도록 한다. 한 번 회전이 끝나면 2. 각 좌표마다 상, 하, 좌, 우 ..