작심 24/7

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 말을 이..

9202번: Boggle 문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle�� www.acmicpc.net 단어 사전을 만들 때 트라이 알고리즘을 이용하여 트리를 만들면 트리 생성 시 O(L*M), 탐색 시 O(L) (L : 제일 긴 문자열의 길이, M : 총 문자열의 수) 로 빠르게 문자열을 탐색할 수 있다. Boggle 보드의 모든 칸마다 가로, 세로, 대각선으로 인접한 칸을 DFS로 글자 수 1부터 8까지 탐색한다. 탐색하면서 사전에 이 단어가 있는지 찾는데 해당 단어가 있다면 set에 있는 단어인지 체크해준 뒤 (중복 찾기 방지 위해) s..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 일반적인 방법으로 구간의 합을 구하면 O(N)이지만 이 문제에서는 시간 초과가 걸릴 가능성이 아주 높기 때문에 O(logN)인 세그먼트 트리를 이용하여 구해야 한다. 일차원 배열을 이용하여 이진 트리를 만드는 데 계산을 편하게 하기 위해서 루트를 인덱스 1로 잡고 왼쪽 노드는 부모 노드 * 2, 오른쪽 노드는 부모 노드 * 2 + 1 의 형태로 지정한다. 루트 노드를 반으로 나누어 구간 A, 구간 B..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 블록을 옮기는 방향에 따라 다르게 검사하며 1. 위로 옮길 때 -> 각 열 위에서부터 검사 2. 아래로 옮길 때 -> 각 열 아래에서부터 검사 3. 왼쪽으로 옮길 때 -> 각 행 왼쪽에서부터 검사 4. 오른쪽으로 옮길 때 -> 각 행 오른쪽에서부터 검사 같은 숫자가 연속해서 나오면 (빈칸 무시) 그 두 숫자를 더한 값을 큐에 넣고 같은 숫자가 연속하지 않을 때는 그 숫자만 큐에 넣는다. 한 줄의 검사가 끝나면 큐에 있는 숫자를 보드판에..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net ▷다른 방식 풀이 보러가기 상, 하, 좌, 우 방향으로 굴리면서 DFS 한다. 빨간 구슬과 파란 구슬이 일직선 상에 있을 경우 order 함수를 통해서 어느 구슬 먼저 굴려야 할지 판단해준 뒤 그 순서에 따라서 다음 경우에 맞게 처리해준다. 1. 빨간 구슬이 구멍에 들어가건 안 들어가건 상관없이 파란 구슬이 구멍 안으로 들어가는 경우 -> 실패이므로 구슬들의 위치만 원 상태로 복귀 후 다음 방향으로 넘어감(cont..