목록알고리즘 (89)
개발자 김수진
[문제] www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net [풀이] 길이가 N인 수열이 주어지고 수열의 합의 최댓값을 구하는 문제. 숫자끼리 서로 묶어서 곱하여 더할 수 있다. 단 모든 수는 한번만 묶거나, 묶지 않아야한다. 큰 수 끼리 곱할수록 값이 더 커지므로 처음에는 vector만 사용해서 풀었다. 음수, 양수를 따로 벡터에 저장한 뒤 정렬하여 풀었는데 틀렸습니다가 나오길래 priority_queue를 사용해서 풀었다. priority_queue는 기본..
[문제] www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net [풀이] 모눈종이 위에 치즈가 존재하고 , 치즈가 공기와 접촉하는 변이 2개 이상일 경우 한시간 뒤에 녹게된다. (치즈 내부에 있는 치즈 공간은 공기와 접촉하지 않는 것으로 가정한다. ) 이 때 치즈가 모두 녹는데 걸리는 시간을 구하는 문제이다. BFS를 사용해 외부 공간을 queue에 저장하였다. queue에서 하나씩 pop 할 때마다 해당 좌표의 상하좌우 중에서 치즈가 존재하는지 확인한다...
[문제] www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net [풀이] S층에서 G층으로 가기 위해 눌러야 하는 버튼 수의 최솟값을 구하는 문제이다. BFS를 사용해 풀 수 있었다. visited 배열을 사용해 이미 방문한 층이라면 넘어가고 처음 방문한 층이라면 이전 층의 버튼 수 +1 을 저장한다. 이렇게 while문을 진행하다가 G 층을 만나면 버튼 수를 출력하고 BFS 함수를 return 한다. queue가 empty가 되어 while문이 끝나는 경우 엘레베이터로 이동할..
[문제] www.acmicpc.net/problem/11559 11559번: Puyo Puyo 현재 주어진 상황에서 몇연쇄가 되는지 출력하라. (하나도 터지지 않는다면 0을 출력하면 된다.) www.acmicpc.net [풀이] 상하좌우 중에서 같은 색깔의 뿌요가 4개 이상 존재한다면 뿌요는 터지게 된다. 뿌요들이 터지고 나서 위에 다른 뿌요들이 있다면 중력의 영향을 받아 차례대로 아래로 떨어지게 된다. 먼저 BFS 함수에서 상하좌우에 같은 색깔의 뿌요가 존재하는지 확인한다. 존재한다면 vector에 push 하여서 queue가 empty가 될 때까지 진행한다. while문을 빠져나와서 벡터의 사이즈가 4보다 크거나 같다면 뿌요가 터질 수 있는 조건을 성립하므로 뿌요가 존재하는 위치의 값을 0으로 upd..
[문제] www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net [풀이] 하반기 어느 기업 코테에서 굉장히 이 문제와 유사한 문제가 나왔었다. 현재 위치를 기준으로 왼쪽과 오른쪽으로 나누고 그 중에서 가장 큰 값을 left, right 변수에 저장한다. left와 right 중에서 작은 값을 고르고 여기서 현재 블록의 높이를 빼주면 해당 블록의 고이는 빗물의 양이 된다. 위와 같은 방식으로 두번째 블록부터 마지막 블록 전까지 반복해주면 된다. [코..
[문제] www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [풀이] DP 배열을 2차원을 선언하여 풀었다. DP[i][j]는 i자리 수에서 마지막 숫자가 J인 경우의 수를 나타낸다. 예를 들어 DP[2][2]는 'X2'인 경우로 12,32가 있으므로 2이다. 따라서 계단 수를 구하는 것이므로 점화식을 아래와 같이 세울 수 있다. DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]; 단 , j가 0이거나 9인 경우 따로 예외처리 해줘야된다. [코드] #include #define MAX 101 #define MOD 1000000000 using namespa..
[문제] www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net [풀이] 고슴도치가 비버의 굴로 이동해야 하는데 물이 있거나 돌이 있는 곳으로는 움직일 수 없다. 물은 매 분마다 인접한 곳으로 퍼진다. 단 , 비버가 존재하는 곳이나 돌이 존재하는 곳으로는 퍼질 수 없다. 이 때 최단 거리를 구하는 문제. 고슴도치의 이동경로를 저장하는 visited 배열과 물, 돌의 정보를 저장하는 map을 선언했다. BFS 함수의 while 문에서 물이 먼저 퍼지고 그 다음에 고슴도치가 움직이..
[문제] www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 미로의 정보가 입력으로 주어지고 시작점 (1,1)에서 도착점(N,M)까지의 최단거리를 구하는 문제이다. 1은 이동할 수 있는 칸을 의미하고, 0은 이동할 수 없는 칸을 의미한다. BFS를 사용해 풀었다. 다음 위치의 값이 1인 경우에만 좌표를 queue에 저장하였고, 이미 방문했던 곳이라면 queue에 담지 않았다. 실수했던 부분이 BFS는 동시에 움직이므로 최단거리를 구하는 경우 재방문 하지 않아도 된다. [코드] 시간 :..