어흥

문제 링크: https://www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net 1. 주의할 점 - 경우의수를 직접 구현해보려다가 실패했다. Set도 생각해 봤지만 그 팀의 가능한 승무패인지 확인만 해줄 뿐 그 이상의 가치는 없다. 즉, DFS로 풀자 2. 구현 - 토너먼트 형식으로 이루어져 있으므로, A팀과 B팀이 붙을 수 있는 경우의 수를 미리 구하여 T1[], T2[]에 넣는다 - 각 라인별을 6등분해서 3개씩 입력받아 한팀에 대한 정보를 Win[], Draw[], Lose[]에 담는다 - 만약 전체 팀의 경기수가 30이 안된다면 잘못된 경우로 간주한다(N*(N-1)번 만큼 경기가 이뤄져야 한다. 양쪽의 입장에서 간주하므로 2로 나누지 않는다) - DF..

문제 링크: https://www.acmicpc.net/problem/14925 14925번: 목장 건설하기 랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다. 그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미 www.acmicpc.net 1. 주의할 점 - DP를 통해 해결한다 - 왼쪽, 위, 왼쪽위 대각선을 살핀다(처음엔 오랜쪽으로 했는데 바꿨다) 2. ..

문제 링크: https://www.acmicpc.net/problem/3108 3108번: 로고 문제 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 �� www.acmicpc.net 1. 주의할 점 - 문제를 DFS+BFS를 이용하여 푸는 방법도 있지만, 제가 푼 방법은 범위를 비교하고 만약 서로 겹치는 점이 있다면 부모를 같게 하는 Disjoint-set 방법으로 해결했다 - 초기 상태 (0,0)에서 고개를 내리고 있으므로, (0,0)에 대한 정보를 포함시키고 시작해야한다. 1.5 범위 비교 - 범위 비교할때 다음과 같은 6가지의 경우만 겹치지 않는다고 판단했다 2. 구..

문제 링크: https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다 www.acmicpc.net 1. 주의할 점 - 무조건 H-G 도로를 지나가고 후보지까지 최단경로를 갱신했다면 정답에 포함한다 - 매 TC마다 초기..

문제 링크: https://www.acmicpc.net/problem/1865 1865번: 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 www.acmicpc.net 1. 주의할 점 - 음의 가중치인 간선이 존재하기 때문에, 벨만포드 알고리즘을 사용한다 - 시작 Node가 정해져 있지 않아서 D..

문제 링크: https://www.acmicpc.net/problem/13334 13334번: 철로 문제 집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 www.acmicpc.net 1. 주의할 점 - N^2만큼 확인하는 코드를 작성하지 않도록 한다. 우선순위큐나 Set을 사용한다(물론 중복값이 있을 수 있으므로 멀티셋 사용) - 각각에 대한 정렬방식을 미리 정해둔다 2. 구현 - 입력받는 수를 우선순위큐 PQ에 저장하며, 도착지점의 오름차순이 1순위이며 시작지점의 오름차순이 2순위다(도착지점이 같다면) - 우선순위큐에서 1개씩 빼며, 시작지점과 도착지점의 ..

문제 링크: https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 1. 주의할 점 - 소수점 12자리 출력 - cout > num; result = 9223372036854775807; for (int i = 0; i > x[i] >> y[i]; } vector v; for (int i = 0; i < num / 2; i++) v.push_back(0); for (int i = 0; i < num / 2; ..

문제 링크: https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 1. 주의할 점 - 전역변수로 선언된 배열들을 잘 초기화해줘야 한다 (While문의 중간에 break걸리면 Pre값이 ..