HTD

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 3차원 DP를 사용하여 이 문제를 해결하였다. > 발상 처음 혹은 마지막 집을 제외하면, 영향을 미치는 범위는 인접한 집뿐이라는 것을 알 수 있다. 이를 통해 O(N)의 반복과 같은 접근법을 사용할 수 있다고 판단하였다. 그리고 중요한 요소가 있는데, 바로 0, N-1번째 집이다. 만약 짜게 될 코드가 0부터 시작해서 N-1에 도달하는 식이라면, 분명히 인덱스가 0인 ..

https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net #include #include #include #pragma warning(disable:4996) #define INF 101 typedef struct Position { double x, y; } Position; typedef struct Metadata { int n; Position* obj; double** graph; } Metadata; typedef struct Pair..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net #include #include #pragma warning(disable:4996) #define INF 10000001 typedef struct Node { int val; struct Node* next; } Node; typedef struct Vertex{ Node* header; int hIndex; int dist; } Vertex; typedef struct Edge { int a, ..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct Node { int val; struct Node* next; } Node; typedef struct Vertex { Node* header; int in; } Vertex; typedef struct Edge { int a, b; } Edg..

#include #include #include #pragma warning(disable:4996) typedef struct Node { int value; struct Node* next; } Node; typedef struct Vertex { Node* header; } Vertex; typedef struct Edge { int v1; int v2; int w; } Edge; typedef struct Metadata { Vertex** vertices; int verticesCount; Edge** edges; int edgesCount; } Metadata; typedef struct Pair { int a, b; } Pair; typedef struct PriortyQueue { Pair..

https://www.acmicpc.net/problem/16975 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net - 배경 Segment Tree의 Lazy Propagation을 안다는 전제로 글을 작성하였으니, 해당 개념에 대해서는 다음 링크를 참조하자. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0-..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net - 풀이 구현해야할 것은 크게 2가지다. 한 줄에서 가장 위에 있는 상어를 잡는 catchShark()와, 상어들을 이동시키는 moveSharks() 함수이다. 전자는 매우 간단하게 구현이 가능하다. 하지만 문제는 후자이다. moveSharks() 함수는 모든 살아있는 상어들을 반복문으로 돌면서, 각각의 위치와 속도, 그리고 방향에 따라 nextPosition을 구해준다. 다음..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net - 관찰 처음에 든 생각은, 모든 벽들부터 시작하는 탐색을 해주는 것이었다. 하지만 이것은 시간복잡도가 너무 크다. 예제 입력 2를 살펴보자. 위와 같이 구분되는 각각의 공간들을 묶어서 값을 저장하고, 이렇게 한 이후에, 모든 벽들에 대해서 (인접한 공간들의 크기의 합) + 1을 해주면 된다. - 풀이 1. 탐색은 2개로 분류된다. 첫번째는 공간의 크기를 조사하는 탐색이며, ..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net - 관찰 단순히 rotate() 함수 하나 만들어서 cube[6][3][3]의 데이터를 적절히 변화시키기만 하면 된다. 하지만 구현이 그렇게 단순하지는 않다. 총 2개의 사항을 구현해야한다. 첫째로, 하나의 면을 돌렸을 때 영향을 받는 다른 4개의 면의 데이터 변경이며, 두번째로, 돌린 면의 3x3의 회전이다. 또한 clockwise/inverse라는 방향도 고려해야하는데, 사실 clockwise ..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net - 관찰 여러 경우에 대한 그림을 그려보면 알겠지만, (0, 0)~(N-1, M-1)로 시작하는 순차적인 탐색을 해보면, 이전 탐색과 동선이 겹치는 경우가 있다. 이 경우에는 하나의 '그룹'으로 묶을 수 있으며, 모든 탐색을 마친 뒤 최종적으로 남는 그룹별로 SAFE ZONE을 설치하면 된다. - 풀이 0. count 변수에 '그룹'의 갯수를 저장하며, 이것을 ..