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..

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이를 사용하는 문제지만 map을 활용해서 접두사 트리를 만들고 전화번호를 만드는 중에 이미 존재하는 전화번호가 있다면 YES 아니면 NO를 출력해주면 된다. map을 로 선언하고 string 부분은 전화번호, bool 부분은 완성된 전화번호인지? 를 판단하는 변수다 이런 식으로 처리해줘서 중간에 2가 나온다면 접두사에 완전한 전화번호가 존재한다는 뜻이니 NO를 출력해주면 된다. 1 2..