작심 24/7

16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 쉽길래 대충 짜고 제출했다가 시간 초과로 여러 번 낭패 본 쉽지 않은 문제이다. sort로 정렬하기 전에 죽은 나무를 제외시키는 것이 관건인 것 같다. 이차원 벡터를 이용하여 나무들을 저장해주었다. 봄과 여름 각 칸에 있는 모든 나무들을 검사한다. 양분을 먹을 수 있는 나무는 살 수 있으므로 큐에 나이를 넣어주고 양분을 먹지 못하는 나무는 양분이 되므로 나이/2 값을 양분 변수에 넣어준다. 현재 칸의 모든 나무들의 검사가 끝나면 죽은 나무를 걸러주..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net BFS를 이용하여 상어 크기와 같은 물고기가 있거나 빈칸인 공간으로 이동하면서 상어 크기보다 작은 물고기를 발견하면 우선순위 큐에 BFS의 깊이(걸린 시간), x좌표, y좌표를 넣어준다. 탐색을 다 마치고 돌아와 우선순위 큐가 비어있으면 먹을 수 있는 물고기가 없는 것이므로 종료 후 최종 시간 출력, 비어있지 않으면 큐 안에서 1. 깊이(걸린 시간)가 가장 작은 순서대로 2. x좌표가 가장 위에 있는 순서대로 3. y좌표가 가장 왼쪽에 있는 순서대로 오..

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

17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 두 선거구로 나눌 때 각 선거구 안에 있는 영역들은 모두 연결되어 있는 상태여야 한다. 그러므로 두 선거구로 나눌 수 없는 경우는 연결되어 있는 그룹이 세 개 이상일 때이므로 이 경우를 가려주기 위해 먼저 BFS로 연결된 그룹이 몇 개인지 세어준다. 3개 이상일 경우 -> -1 출력 2개일 경우 -> 두 그룹이 각각 선거구이므로 이때 인구의 차 출력 1개일 경우 -> 모두 연결된 상태이므로 다음 단계 넘어감 두 선거구로 나누는 방법은 N개 중에서 K개를 순서 상관없이 뽑는 조합으로 구..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net BFS, 완전 탐색 문제이다. 무조건 3개의 벽을 세워야 하므로 빈칸 n개 중 3개를 순서 상관없이 고르는 조합으로 구현하고 큐로 구현한 BFS로 바이러스의 개수를 구한 뒤 안전 영역의 개수 = 빈칸 개수 - 바이러스의 개수 - 3 의 최댓값을 출력해주면 된다. #include #include #include #include using namespace std; int N, M, cnt, res, x, y, tmp; int arr[8][8], dx[4] ..

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 연산 횟수를 1씩 증가해주며 현재 횟수로 만들 수 있는 숫자들을 모두 임시 큐에 넣어주고 메인 큐가 empty할 때까지 반복한 뒤 빠져나오면 임시 큐의 값들을 전부 메인 큐에 넣어준다. 연산 횟수가 K가 되면 빠져나와 최댓값을 출력해주는데 최댓값의 default를 -1로 해주면 연산을 K번 할 수 없는 경우엔 최댓값이 변하지 않아 문제에서 바라는 대로 -1을 출력할 수 있다. ex) 숫자는 10이고 K는 1일 때 이때 주의할 점은 방문 체크하는 부분이다. 현재 메인 큐를 다 비우고 나면 다음 메인 큐에서 할 연산은 현재 메인 큐와 ..

1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 관리를 편하게 하기 위해 이차원 배열로 되어 있는 값들을 일차원으로 생각하면 123456780 으로 나타내는 게 목표가 된다. 빈칸의 상하좌우를 검사해주며 빈칸과 숫자를 교환하고 그 값이 목표와 일치하면 같이 저장되어 있던 횟수를 출력, 큐가 empty할 때까지도 목표를 못 만나면 -1을 출력한다. 큐에 값을 집어넣어줄 땐 빈칸과 숫자의 교환을 쉽게 하기 위해서 string 타입으로 숫자를 넣어주는데 이때 0의 위치(빈칸 위치)와 그 숫자까지 가는데 걸린 횟수도 같이 넣어준다. ex) ("360812745", 2, 이전 수의 횟수 + 1)..

9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스� www.acmicpc.net D, S, L, R 각 경우에 맞게 값을 변형시킨 다음 그 값이 될 때까지 어떤 과정이 있었는지 배열에 저장한 뒤 그 값이 B가 되면 출력하면 된다. 여기서 주의할 점은 네 자리 레지스터라서 'L 적용 시 123이니까 231이겠지'라고 생각하면 안 된다. 123은 0123으로 취급하여 L 적용 시 1230이 된다. 처음에 잘못 생각하고 string으로 복잡하게 변형시켜주다 시간 초과 걸렸었다. 이 점만 주의해주면 굳이 string 쓸 필요 없이 ..