프로그래밍
BOJ 15684 · 사다리 조작
알고리즘 분류 : 브루트 포스, 백트래킹 사다리를 적절히 만들어서 사다리 타기를 해야하는 문제다. 가로줄은 최대 3개까지 놓을 수 있고, 최솟값을 출력하면 된다. 출발한 사다리 번호(세로줄)와 도착한 사다리 번호가 모두 같아야 사다리를 제대로 탄 것이다. 가능한 사다리를 모두 만들면 시간 초과될 수 있으므로, 적절히 백트래킹을 하여 경우의 수를 줄여야 한다. 주어진 입력을 통하여 H*N 사이즈의 사다리를 만든다.A번 세로줄과 A+1번 세로줄의 사이에 B번 가로줄로 연결한다면, 사다리 [A][B]를 연결(1)한다.아래 그림을 확인. 재귀 함수를 이용하여 가능한 사다리를 만든다.사다리에 가로줄을 만들 때, 가로줄은 연속해서 만들지 않아도 되는 것에 유의한다.만약 현재 위치가 (i, j)이고, 사다리가 연결되..
BOJ 14890 · 경사로
알고리즘 분류 : 시뮬레이션 경사로를 만들어서 지나갈 수 있는 길의 개수를 구하는 문제다. 문제에 주어진 조건에 따라 그대로 구현해야 한다. 지나갈 수 있는 길을 확인하기 위해 가로 방향과 세로 방향을 구분해서 순차 탐색해야 한다.먼저 현재 칸의 높이 A와 다음 칸의 높이 B를 구하고, B-A를 D라고 하자.D가 0이라면, 길의 높이가 같은 경우이다.D가 1이라면, 올라가는 경사로가 필요한 경우이다.D가 -1이라면, 내려가는 경사로가 필요한 경우이다. 길의 높이가 같다면 (D == 0), 카운트를 1 증가시킨다. 카운트는 경사로의 길이와 비교하기 위해 필요하다.올라가는 경사로라면 (D == 1), 카운트가 경사로의 길이 L 이상인지 확인한다. 카운트가 L 이상이라면, 경사로를 놓을 수 있는 경우이므로, ..
BOJ 15662 · 톱니바퀴 (2)
알고리즘 분류 : 시뮬레이션 T개의 톱니바퀴를 회전시키는 시뮬레이션 문제다. BOJ 14891번 '톱니바퀴'와 유사한 문제이다. 자세한 내용은 이전 문제 참조. 톱니바퀴의 수는 T개이다. 최대 1,000개.정답은 12시 방향에 S극(1)이 몇 개 있는지만 세면 된다. C++ 소스코드 #include int a[1000][8]; int t, k, ans; void rotate(int n, int d) { int t[8]; if (d == 1) { for (int i=0; i
BOJ 14891 · 톱니바퀴
알고리즘 분류 : 시뮬레이션 톱니바퀴의 회전 동작을 시뮬레이션하는 문제다. 문제는 어렵지 않으나, 회전 방향이 헷갈려서 귀찮은 문제다. 입력으로 주어지는 톱니바퀴를 기준으로 시작한다.톱니바퀴의 인덱스는 12시 방향부터 시계방향으로 [ 0 1 2 3 4 5 6 7 ] 로 둔다.1. 기준 톱니바퀴의 왼쪽에 톱니바퀴가 있다면, 기준 톱니바퀴의 왼쪽 톱니(인덱스 6)와 왼쪽 톱니바퀴의 오른쪽 톱니(인덱스 2)를 비교한다.2. 극이 다르다면, 왼쪽 톱니바퀴의 회전 방향을 기준 톱니바퀴의 반대 회전 방향으로 저장한다.첫 번째 톱니바퀴까지 1~2 과정을 반복하여, 회전 방향을 저장해둔다.3. 기준 톱니바퀴의 오른쪽에 톱니바퀴가 있다면, 기준 톱니바퀴의 오른쪽 톱니(인덱스 2)와 오른쪽 톱니바퀴의 왼쪽 톱니(인덱스 6..
BOJ 3190 · 뱀
알고리즘 분류 : 시뮬레이션 주어진 조건을 그대로 구현하는 시뮬레이션 문제다. 뱀이 사과를 먹으면서 길이를 늘리는 게임을 구현해야 한다. 뱀의 시작 위치는 (0, 0)이며 시작 방향은 오른쪽이다. 범위 (0, 0) ~ (N-1, M-1) 기준뱀의 이동 좌표를 저장하기 위해 Queue를 사용한다.매초, 뱀이 현재 방향으로 머리를 먼저 한 칸 앞으로 옮긴다. 머리 위치를 큐에 push 한다.이동한 칸에 사과(1)가 있을 경우, 꼬리를 줄이지 않는다.이동한 칸이 빈칸(0)이라면, 꼬리를 한 칸 줄인다. 큐에서 꼬리 칸을 pop 한다.뱀의 좌표는 (2)로 둔다.이동 후에, 방향 전환을 해야 한다면, 주어진 입력에 따라 방향을 바꾼다.이동할 때 벽에 부딪히거나(맵을 벗어난 경우), 뱀 자신(2)에게 부딪히면 종료..
BOJ 14499 · 주사위 굴리기
알고리즘 분류 : 시뮬레이션 문제에 주어진 조건에 따라 주사위를 굴리는 문제다. 먼저 주사위의 숫자를 임의로 고정시킨다.동서남북 방향에 따라 바뀌는 주사위의 숫자를 설정한다.방향에 따라 시뮬레이션 한다.아래의 그림을 참조. 주사위 모양에서 0이 윗면이고, 5가 바닥면이다. C++ 소스코드 #include int n, m, x, y, k; int a[20][20]; int dice[6], temp[6]; const int direct[4][6] = { {2, 1, 5, 0, 4, 3}, {3, 1, 0, 5, 4, 2}, {4, 0, 2, 3, 5, 1}, {1, 5, 2, 3, 0, 4} }; const int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0}; void sol..
BOJ 13458 · 시험 감독
알고리즘 분류 : 시뮬레이션 문제에 주어진 조건 그대로 구현하면 된다. 총 감독관은 항상 1명 존재하므로, 문제의 정답은 N명 이상이다.부 감독관은 각 시험장에 남아있는 응시자의 수를 부 감독관 수로 나눠서 구할 수 있다. C++ 소스코드 #include int n, b, c; int a[1000000]; long ans; void solve() { for (int i=0; i= b) { int d = a[i]-b; ans += (d%c == 0 ? d/c : d/c+1); } } printf("%lld\n", ans+n); } int main() { scanf("%d", &n); for (int i=0; i= b: d = a[i]-b ans += d//c if d%c == 0 else d//c+1 pr..
BOJ 14502 · 연구소
알고리즘 분류 : 브루트 포스, DFS 연구소에 벽을 3개 세워서 바이러스를 최대한 덜 퍼트리고, 안전 영역의 최대 크기를 구하는 문제다. N*M은 최대 64이므로, 벽을 두는 모든 경우의 수를 구해서 최대 크기를 확인해 볼 수 있다. 우선 입력으로 받은 맵에 벽을 3개 세워야 한다.벽(1)은 빈 칸(0)에만 세울 수 있다. N*M을 순회하면서 빈 칸이라면 벽을 둔다.벽을 두는 함수는 재귀로 구현한다. 벽 카운트를 세면서 3이 되면, DFS를 통해 빈 칸에 바이러스(2)를 퍼트린다.바이러스를 퍼트리면서, 바이러스가 퍼진 칸을 센다.바이러스 칸이 최소가 될 때, 안전 영역의 크기가 최대가 된다. C++ 소스코드 #include #include #include using namespace std; int n..