목록분류 전체보기 (104)
개발자 김수진
[문제] www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net [풀이] 지훈이가 미로를 빠져나오는데 최소 시간을 구하는 문제로 아래 문제와 굉장히 유사하여 쉽게 접근할 수 있었다. www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmi..
[문제] www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net [풀이] 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 서로 완전 반대의 상태가 된다. 따라서 하나의 상태만 구해놓고 반대로 생각하면 된다. 검은색은 1, 흰색은 0으로 구분하여 int형이 아닌 bool형 배열을 사용했다. 먼저 맨 왼쪽 위 칸이 검은색인 경우를 구해서 b라는 배열에 저장했다. 그리고 반복문을 통해 모든 좌표에 대해서 (x,y)가 맨 왼쪽 위 칸이 되어 8*8 크기..
[문제] www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net [풀이] 구현 문제로 k번의 이동 후 , 남아있는 파이어볼의 질량을 구하는 문제이다. 파이어볼이 이동하고 , 파이어볼이 2개 이상 존재하는 곳은 파이어볼이 하나로 합쳐진 뒤 4개로 나누어진다. 따라서 파이어볼이 이동하는 move 함수와, 파이어볼이 나누어지는 solve 함수를 따로 구현하였다. 먼저 입력받은 파이어볼의 정보를 fire라는 구조체 벡터에 저장한다. ..
[문제] www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [풀이] 처음에는 DFS 방식으로 접근을 하였다. 하지만 생각을 해보니 DFS 함수의 탈출 조건을 설정할 수 없었다. 따라서 다른 방법을 생각하던 중 BFS 방식으로 풀어야겠다고 생각했다. BFS 방식에서 처음 입력 값의 빨간, 파란 공의 위치를 시작으로 상,하,좌,우 방향으로 움직이도록 하였다. 이 때 파란 공이 골에 들어가거나, 이미 방문했던 위치라..
[문제] www.acmicpc.net/problem/2931 2931번: 가스관 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. www.acmicpc.net [풀이] 맞아서 기분이 좋긴 하지만 뭔가 찝찝하다. 3 5 . . . . . . M . Z . . . . . . 위와 같은 예제는 답이 제대로 나오지 않는다. 시작점을 기준으로 DFS 함수를 통해 한칸씩 나아가도록 하였다. 이 때 현재 위치의 값이 '.' 이라면 solve 함수에서 해당 위치에 들어갈 값을 찾도록 하였다. [코드] 시간 : 0ms #include #define MAX 26 using namespace ..
[문제] www.acmicpc.net/problem/1756 1756번: 피자 굽기 월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 www.acmicpc.net [풀이] 오븐의 지름, 피자 반죽의 지름이 주어지고 마지막 피자 반죽의 위치를 출력하면 된다. 처음에는 완전 탐색으로 풀까 생각했는데 N,D의 최댓 값이 300,00이라서 시간초과가 나오게 된다. 따라서 dp 방법을 사용해 구현했다. depth 라는 배열에 해당 깊이에 구워질 수 있는 피자 지름의 최댓값을 저장했다. 문제 예제로 보면 7 3 5 6 4 3 6 2 3 3 2 5 depth 배열의 값은 5 5 4 ..
[문제] www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 수빈이의 위치 N, 동생의 위치 K가 입력으로 주어지고 수빈이가 동생을 찾는 최단경로를 구하는 문제. 이 때, 수빈이는 현재 위치 X 에서 X-1,X+1,2*X로만 움직일 수 있다. 최단경로를 찾아야 하므로 BFS를 사용했다. 현재 위치 X에서 X-1,X+1,2*X로 움직이도록 하였고 visited 배열을 사용해 재방문 하지 않도록 했다. 또한 경로도 구해야 ..
[문제] www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net [풀이] 두 보물간의 최단거리를 구하는 문제. 최단거리를 구하는 문제이길래 BFS를 사용해서 풀려고 했다. 하지만 보물의 위치가 어딘지 몰라서 시작점과 도착점을 설정하는 데 있어 어려움을 겪었다. 생각해보니 map의 최대 사이즈는 50*50이라서 모든 육지에 대해서 시작점으로 잡고 최단거리를 구해도 되겠다고 생각을 하였다. 따라서 모든 육지에 대해 출발점으로 잡고 BFS 함수에서 최단거리를 구해 그 중에서..