2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 분명 쉬운 문제인데 오래 걸렸다. 문제 분류를 보니 스택도 있던데, 나는 그냥 구현으로 해결했다. 1. 우선 정보를 입력받고, L(왼쪽 면의 위치)을 기준으로 오름차순으로 정렬한다. 2. 최고 높이를 가진 기둥을 찾아 그 기둥의 인덱스를 기록해 둔다. 3. 0부터 최고 높이를 가진 기둥의 인덱스까지 오름차순으로 검사. 3-1. 이전 최고 높이보다 높거나 같은 높이를 가진 기둥을 찾을 때마다 넓이를 정답에 더하고, H와 L을 갱신. 4. 마지막 인..
전체 글
2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 싸피에서 알고리즘 배울 때도 틀렸던 문젠데, 또 틀렸다... 워낙 유명한 문제라 미트마스킹을 써야 한다는 건 알고 있었는데, 풀지 못했다 예전에 메모했던 것과 참고한 풀이(링크)를 보고 생각한 이 문제의 핵심은, 출발 위치를 고민할 필요가 없다는 것이다. (처음으로 다시 돌아와야 한다는 것 > 사이클을 이룬다는 것 > 경로가 정해지면 사이클의 어느 도시에서 출발하든 비용은 같음 > 출발 위치를 고민할 필요가 없다) dp 배열..
1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 작년에 푼 문제인데 다시 한번 풀어봤다. 도시의 수가 적고, 같은 도시를 방문해도 된다는 부분에서 어떻게든 목적지로 가기만 하면 된다고 생각해 플로이드 워셜로 A도시에서 B도시로 갈 수 있는지를 모두 구해놓으면 된다고 생각했다. 코드 #include int N, M; bool has_road[201][201]; int travel[1001]; int main() { std::cin >> N >> M; int cell; for (int i = 1; i < N + ..