목록알고리즘 (89)
개발자 김수진
[문제] www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [풀이] 언니의 위치 N, 동생의 위치 K가 입력으로 주어지고 언니가 동생을 찾는데 걸리는 최소 시간을 구하는 문제이다. 숨바꼭질4( www.acmicpc.net/problem/13913) 와 굉장히 유사한 문제이다. BFS를 사용해서 풀었다. 원래 BFS는 방문 체크를 하여 이미 방문한 곳이라면 다시 방문하지 않는다. 하지만 이 문제에서는 순간이동이 있으므로 이미 방..
[문제] www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net [풀이] 추의 무게가 주어지고 추를 사용해서 측정할 수 없는 무게의 최솟값을 구하는 문제이다. 아무리 생각해도 다 더하는 방법 말고는 생각이 안나서 풀이를 봤다. 풀이는 그리디 알고리즘으로 구현했다. 주어진 추의 무게를 오름차순으로 정렬하고 현재까지의 합을 sum이라고 할 때, 더하려는 추의 무게가 sum+2보다 크거나 같다면 sum+1의 무게는 측정할 수 없다. 풀이를 보니 이해는 되지만 문제를 풀면서 어떻게 ..
[문제] www.acmicpc.net/problem/5624 5624번: 좋은 수 정수 N개로 이루어진 수열 A가 있다. 이때, i번째 수가 그 앞에 있는 수 세 개의 합으로 나타낼 수 있을 때, 그 수를 좋다고 한다. (같은 위치에 있는 수를 여러 번 더해도 된다) 수열이 주어졌을 때 www.acmicpc.net [풀이] N개의 수열이 입력으로 주어지고, 하나의 숫자가 앞의 3개의 숫자를 더해서 나타낼 수 있을 때 좋은 수라고 한다. 이 때 입력에서 좋은 수의 갯수를 구해서 출력하면 된다. 좋은 수인지 판단하려는 숫자고 D라고 하면 A+B+C=D를 만족하는 수를 찾으면 된다. 좀더 다르게 생각하면 A+B=D-C 를 만족하는 D를 찾으면 된다. 따라서 D 이전의 숫자들 중에서 A+B의 값을 negativ..
[문제] www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net [풀이] 입력으로 주어진 알파벳을 숫자로 바꿔서 알파벳 합의 최댓값을 구하는 문제이다. 먼저 해당 알파벳이 몇번째 숫자로 얼마나 나왔는지에 따라 알파벳에 대한 숫자를 지정했다. 예를 들어 ABCD라면, A->9, B->8, C->7, D->6 이렇게 큰 자릿수가 큰 숫자를 가지도록 해야 최댓값을 구할 수 있다. 따라서 visited 배열에 해당 알파벳의 자릿수를 저장하였다. 위의 예시로는 visi..
[문제] 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 방식에서 처음 입력 값의 빨간, 파란 공의 위치를 시작으로 상,하,좌,우 방향으로 움직이도록 하였다. 이 때 파란 공이 골에 들어가거나, 이미 방문했던 위치라..