본문 바로가기

알고리즘66

[백준 2638] 치즈 (C++) A. 문제설명 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 위 그림과 같은 N*M 땅이 존재 2. 땅의 검은 부분에는 치즈가 존재, 흰 부분에는 공기가 존재 3. 치즈는 상/하/좌/우로 2면이상 공기와 맞닿으면 1초이후 사라짐 4. 그러나 치즈에 둘러쌓인 공기부분은 치즈에 영향을 주지 않음 5. 치즈는 배열의 가장자리에는 존재하지 않는다고 할 때, 치즈가 땅에서 없어지기까지의 총 시간을 구하라 B. 접근.. 2020. 10. 21.
[백준 2468] 안전 영역 (C++) A. 문제설명 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 아래와 같은 N*N 크기의 땅이 존재 2. 각 땅에는 높이 값이 주어지고, 이제 해당 지역에 비를 뿌리려고 함 3. 비가 내릴 때, 다음과 같이 특정 높이 이하의 지역들은 물에 잠기는데 이때 물에 잠기지 않은 인접한 지역들을 모아 안전 영역이라고 함 4. 강수량에 따라 특정 높이로 물에 잠기는 지역이 달라질 수 있을 때 최대가 되는 안전 영역의 갯수를 구하라.. 2020. 10. 16.
[백준 9019] DSLR (C++) A. 문제설명 www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 � www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. D/S/R/L 4개의 명령을 수행하는 레지스터가 존재 2. 각 명령에 대한 설명은 아래와 같음 D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 .. 2020. 10. 16.
[백준 6087] 레이저 통신 (C++) A. 문제설명 www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. W*H 크기의 배열이 주어짐 2. 각 배열은 빈칸 '.' 혹은 벽 '*' 으로 이루어짐 3. 여기서 'C'로 표시되는 두 칸이 주어짐 4. 아래 그림과 같이 이 두칸을 레이저로 통신할 수 있게 잇고자 하는데 중간에 거울을 놓아 레이저의 이동방향을 90도 회전할 수 있게 함 7 . . . . . . . 7 . . . . . . . 6 . . . ... 2020. 10. 16.
[백준 1600] 말이 되고픈 원숭이 (C++) A. 문제설명 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. H*W 크기의 배열이 주어짐 2. 원숭이는 0,0의 위치에서 H,W의 위치로 이동하고자 함 3. 원숭이는 기본적으로 상하좌우 인접한 칸으로 이동이 가능하나 아래와 같은 말의 이동을 따라하려 함 x x x x 말 x x x x 4. 말의 이동동선은 다음과 같은데, 원숭이는 해당 이동을 K번 따라할 수 있음 5. 말의 이동방법과 원숭이의 .. 2020. 10. 12.
[백준 16509] 장군 (C++) A. 문제설명 www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 10*9 크기의 장기판이 존재 2. 장기게임에서의 상의 이동은 아래와 같이 8방향으로 가능함 3. 물론, 실제 장기게임 규칙과 같이 해당 이동동선에 말이 존재하면 이동할 수 없음 4. 왕과 상의 위치가 각각 주어졌을 때, 상이 최소이동으로 왕을 잡는 경우를 구하라 B. 접근법 BFS 장기말의 이동의 최단동선 중 왕을 잡는 경우를 찾기 위해 BFS로 구현하였다. 일.. 2020. 10. 12.
[백준 1938] 통나무 옮기기 (C++) A. 문제설명 www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 2020. 10. 10.
[백준 2151] 거울 설치 (C++) A. 문제설명 www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 �� www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. N*N 크기의 땅이 존재 2. 각 배열의 엔트리에는 '.', '!', '#', '*'가 주어짐 3. '*'는 벽으로 빛이 이동하지 못하고, '.'은 아무것도 없는 공간으로 빛이 이동가능하며 '#'은 문으로 빛이 들어오는 지점임 4. 여기서 '!'는 거울이 있는 지점인데 거울을 45도 비스듬하게 놓아 빛의 이동경로를 바꿔줌 5. 주어진 배.. 2020. 10. 9.
[백준 16946] 벽 부수고 이동하기 4 (C++) A. 문제설명 www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. N*M크기의 배열이 존재 2. 해당 배열 안에는 1:벽, 또는 0:빈칸이 입력으로 주어짐 3. 각 벽이 있는 공간에서 인접한 공간으로 벽을 부수고 이동하려고 함 4. 여기서 벽은 맨 처음 하나만 부술 수 있고, 이동가능한 공간은 빈 공간만 5. 이렇게 해서 각각의 벽인 공간에 총 이동할 수 있는 거리를 구할 것 B. 접근법 Has.. 2020. 10. 8.
[백준 2174] 로봇 시뮬레이션 (C++) A. 문제설명 www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 가로 A, 세로 B 크기의 아래와 같은 땅이 존재 2. N개의 로봇의 초기위치 x, y 그리고 현재 바라보는 방향이 각각 주어짐 3. 그리고 M번의 명령이 주어지는데, 각각 해당 명령을 수행하는 로봇의 번호, 명령의 종류, 반복 횟수가 주어짐 4. 여기서 명령의 종류는 아래와 같음 L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 .. 2020. 10. 8.
[백준 19235] 모노미노도미노 (C++) A. 문제설명 www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 아래와 같은 빨간/파란/초록색 보드가 붙어있는 형태의 배열판이 존재 2. 그리고 게임에서는 아래와 같은 형태의 1*1, 2*1, 1*2 크기의 블록을 사용 3. 게임의 규칙은 1번의 그림과 같이 빨간색에 먼저 블록이 배치되고, 해당 도형이 테트리스의 규칙과 같이 파란/초록색 영역으로 우선 이동 4. 도형은 빨간색 영역에 배치된 모양을 유지하여 횡/.. 2020. 9. 30.
[백준 3987] 보이저 1호 (C++) A. 문제설명 www.acmicpc.net/problem/3987 3987번: 보이저 1호 첫째 줄에 시그널을 보내는 방향을 출력한다. (U: 위, R: 오른쪽, D: 아래, L: 왼쪽) 만약, 방향이 여러 가지가 존재한다면, U, R, D, L의 순서 중 앞서는 것을 출력한다. 둘째 줄에는 가장 긴 시간을 출� www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 아래와 같은 N*M 배열판이 존재 2. 배열 내 각 엔트리에는 C(블랙홀), .(빈 공간), / \(행성)이 각각 존재 3. 보이저 1호에서 처음 출발위치에서 시그널을 동서남북의 방향으로 보내 전파시키려고 함 4. 여기서, 시그널이 / \(행성)을 만나면 아래 그림과 같이 방향을 전환하게 됨 5. 그 외에 빈공간을 만나면 방.. 2020. 9. 30.
[백준 19238] 스타트 택시 (C++) A. 문제설명 www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 아래와 같은 N*N 배열판이 존재(흰색이 빈칸, 회색이 벽) 2. 택시 운전자가 M명의 승객을 각각의 목적지에 데려다 주려함 3. M명의 승객들 중, 태울 손님을 고르는 기준은 가장 최단거리, 만약 최단거리인 손님이 여러명이면 최상위 행을 우선으로, 그래도 여러명이면 최좌측 열을 우선으로 선택 4. M명의 승객은 동.. 2020. 9. 21.
[백준 19237] 어른 상어 (C++) A. 문제설명 www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 아래와 같은 N*N 배열판 위에 M마리의 상어가 주어짐 2. 각 상어는 1~M번 번호로 구분되어 초기 위치와 방향이 주어짐 3. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌림 4. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌림 5. 냄새는.. 2020. 9. 21.
[백준 17822] 원판 돌리기 (C++) A. 문제설명 www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제에 대한 자세한 설명은 링크 참조 1. 반지름이 각기 다른 N개의 원판이 주어짐. 각 원판에는 M개의 정수가 적혀짐 2. 각 원판은 1,2, ... ,N번째 원판까지 안쪽부터 바깥쪽으로 끼워짐 3. 각 원판의 엔트리는 (i, j)와 같이 나타나며, 그 규칙은 아래와 같음 (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다.. 2020. 9. 9.