devlog

출처 : 5014번: 스타트링크 (acmicpc.net) 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 방법 경우가 올라가고 내려가는 2경우 밖에 없으므로 bfs를 통해 탐색했다. bfs의 큐를 통해 방문하지 않은 층이라면 내려가는 경우와 올라가는 경우 두 개의 층을 범위가 벗어 나지 않으면 큐에 추가해주었다. 그리고 visited를 활용해 몇번 움직였는지를 저장해 주었다. #include using namespace std; // boj num 5014 int F, S, G, U, D; int visited[10..

출처 : 1946번: 신입 사원 (acmicpc.net) 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 방법 서류심사와 면접시험이 둘 다 어떤 사람보다 낮으면 채용되지 않는다고 문제에 설명되어 있다. 서류심사 등수 기준으로 정렬을 한 뒤 서류심사 1등은 무조건 채용된다. 서류심사 1등의 면접 등수를 temp라는 변수에 저장한뒤 for문을 돌며 temp보다 좋은 등수를 받은 사람이 있으면 이 사람의 면접 등수를 temp에 저장해주고 ans를 +1해준다 이 과정을 for문 끝까지 반복..

출처 : 2589번: 보물섬 (acmicpc.net) 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 풀이 방법 그래프 문제인데 시작점을 여러번 바꿔가면서 bfs를 수행하여야 한다. 그래서 완전 탐색(Brute Force)를 이용하여 육지에서의 거리가 가장 먼 값을 구하여 답으로 출력 해야한다. 여기서 visited에 거리를 저장하는데 시작점을 1로 두어야 다시 시작점을 방문하는 오류를 줄일수 있어 시작점의 visited 값을 1로 설정한뒤 마지막에 답을 출력할때 -1을 해준다. #include using nam..

출처 : 7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 방법 익은 토마토의 인접한 토마토들이 익어가는 것으로 보아 그래프 문제이다. 인접한 단계에 따라 기간이 흘러가므로 bfs문제로 볼 수 있다. 그런데 이 문제는 bfs의 시작점 즉 처음부터 익어있는 토마토가 한 개가 아니므로 시작점을 여러개 해주어야한다. 그러기 위해 입력을 받을 때 처음으로 익어 있는 토마토의 위치를 저장해 둔다. 그리고 bfs를 돌기위해 저장해둔 토마토 위치를 모두 큐에..

출처 : 1932번: 정수 삼각형 (acmicpc.net) 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 방법 삼각형을 위에서부터 내려오면서 자신의 인덱스가 자신이 속한 층내에서 i 번째라면 바로 위층의 i-1,i 번째 인덱스 중 큰 수를 더해주면서 가장 바닥까지 내려와 바닥중 가장 큰 수를 출력하면 된다 #include using namespace std; vector triangle; int N, ans; int main() { cin >> N; triangle.resize(N); for (int i = 0;i < N;i++) { for (int k = 0;k < i+1..

출처 : 12851번: 숨바꼭질 2 (acmicpc.net) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 방법 visited배열에 현재 위치를 방문했는지를 기록하고 하지 않았으면 bfs로 방문하면 된다 bfs를 이용하면 자동적으로 시간이 빠른 것부터 참 색 하여 답에 도착하므로 bfs를 사용하였다 x가 현재위치다. x-1 >=0 이고 x-1 지점을 방문하지 않았더라면 x-1 지점을 방문한다 여기서 현재 위치가 목표 위치보다 작더라도 x-1을 해주어야 한다 왜냐하면 ..

출처 : 18428번: 감시 피하기 (acmicpc.net) 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 풀이 방법 완전 탐색 + DFS로 풀이할 수 있다. 벽을 세우는 경우를 완전 탐색으로 푸는데 시간을 줄이기 위해 빈 공간을 미리 리스트에 저장해둔다 벽이 3개 생성되면 check 함수를 호출하여 각 선생님의 동서남북 방향을 검사한다 while 문을 통해 board안에서의 동서남북중 한쪽씩 방향을 정해서 검사한다. 만약 검사 중 벽이 나타나면 다른 방향으로 넘어가고 검사중 학생이 나타나면 retu..

출처 : 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 방법 DFS로 완전 탐색으로 풀어야 한다. 연산자를 배열로 따로 넣어 두고 각 연산자가 남아 있으면 사용하고 연산자 배열에서 -1을 해주고 dfs를 호출하고 다시 연산자 배열에서 +1을 해주는 백트레킹 방식으로 풀이 하였다. max_num = -987654321 min_num = 987654321 def dfs(index, sum): glo..

출처 : 1068번: 트리 (acmicpc.net) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 방법 DFS함수의 인자로 index를 받고 재귀 호출하는 방식으로 문제를 풀이하였다. 만약 index가 삭제할 노드의 인덱스인 경우 삭제할 노드의 부모 노드의 자식이 1명일 경우(삭제당하는 노드 하나) cnt를 +1 해주었다. 그리고 return을 함으로써 삭제할 노드의 자식은 탐색하지 않았다 index가 삭제할 노드의 인덱스가 아닌데 자식이 empty인 경우에도 cnt를 +1 해주었다. 다음 자식이..

출처 : 3055번: 탈출 (acmicpc.net) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 방법 입력받을 때부터 S와 D 지점의 좌표를 기록하고 water의 좌표 벡터에 기록하였다 BFS를 시작할 때 queue에 water의 좌표를 먼저 추가 해준 후 고슴도치의 위치를 que에 넣어 주었는데 이유는 water을 먼저 BFS 하고 그 길을 고슴도치가 갈 수 있냐 없냐 판단을 하기 위해서 이다 (고슴도치를 먼저 이동시키면 동시에 물이 들어오는 경우 복잡해짐) 그런 후 BFS를 돌며 다음 좌표의 board(땅) ..