개발자 김수진

[문제] 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 방식에서 처음 입력 값의 빨간, 파란 공의 위치를 시작으로 상,하,좌,우 방향으로 움직이도록 하였다. 이 때 파란 공이 골에 들어가거나, 이미 방문했던 위치라..

[문제] 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 ..