www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 생각보다 쉽게 풀었다. 치킨집이 총 13개까지 주어지는 조건을 봤고, 치킨집과 집을 매칭 시키는 것이 combination을 떠올리게 한다. 따라서 그래프 탐색이 아니라 조합, 경우의 수로 접근해봤다. 일단 보자마자 집을 원소로 가지는 a벡터, 치킨집을 원소로 가지는 b벡터를 인자로 받아 각 원소를 \(O(N^2)\)으로 순회하며 가장 작은 치킨 거리를 찾아 리턴해주는 함수를 만들었다. 1..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. deque를 사용하면 앞뒤로 삽입과 삭제를 용이하게 할 수 있다. 일단 방향을 정해주는데 북, 동, 서, 남..

www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 문제는 그리디 하게 접근해야 한다는 것이다. 그냥 지름길이 주어졌다고 해서 지금 길만 탄다면 다른 컴포넌트에 있는 길로 가는 것이 더 빠를 수 있다. 어떻게 접근해야 할까? 핵심은 다익스트라를 돌리면서 현재 위치 + 1 에 지름길이 없다면 우선순위 큐에 cost + 1 로 넣어주는 것이다. 이렇게 되면 자연히 d 이하의 모든 노드를 탐색하면서 지름길이 있다면 지름길을 타고, 아니라면 다음 컴포넌트가 ..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 정사각형을 만족하기 위해서 어떤 규칙이 필요할까? 행렬 i, j 를 기준으로 왼쪽, 위, 왼쪽 위가 모두 1인 것만이 정사각형이 된다. 이걸 확장시켜주면, 최종적인 점화식은 \(D[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1]) + 1\) 이 된다. 물론 조건문으로 현재 위치가 1이고 그 주변도 1임을 미리 따져줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 배낭 문제의 변형이다. 메모리와 비용이 주어지는데 dp테이블을 메모리를 기준으로 채워야 하나? 생각했는데 비용을 기준으로 dp테이블을 채워줘야 한다. 예제를 보면 30 10 20 35 40 3 0 3 5 4 가 주어지는데 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 10 10 40 50 50 60 80 80 85 100 100 115 115 115 135 이런 식으로 테이블을 채워주고 그때..

앞쪽에 있는 기능이 전부 개발되었다면 앞에서부터 기능이 개발되지 않은 것이 나올 때까지 pop 해주고 그 cnt를 answer에 저장해주면 된다. 우선 progresses와 speeds를 전부 큐에 넣어주고 반복문을 통해 0번 위치의 기능을 수행하는 데에 얼마나 걸리는지 세준다. 이후 현재 날 * speed의 front + q의 front가 100보다 크다면 그 기능도 이미 완료되었기 때문에 pop 해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include #include using namespace std; vector solution(vector progresses, vect..