전체 글

https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net [문제] [풀이] 현재 연료상태를 curFuel 이라고 하면 , 이 연료로 어느 주유소까지 갈 수 있는지 검사해야한다. 연료가 많은 순으로 정렬된 우선순위큐를 fuelQ라고 하자. 주유소 거리순으로 정렬한 뒤에 하나씩 뽑아보면서 1. 만약 갈수 있다면 연료큐(fuelQ)에 push 2. 갈수 없다면 2-1. 연료큐가 비어있으면 끝. (연료가 모자라서 갈수 없음..

https://www.acmicpc.net/problem/2152 2152번: 여행 계획 세우기 첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공 www.acmicpc.net [문제] [풀이] SCC + DP 문제이다. 최대한 많이 여행하기 위해선 왔던곳을 경로만 있다면 몇번이든 돌아다녀서 최종적으로 얼마나 돌아다녔는지를 구해야한다. 1. SCC 생성 SCC를 이루고 있는 도시들을 하나의 큰 Node로 취급하는 SCC를 여러개 만들어준다. 2. SCC 그래프 연결 SCC Node 끼리 그래프를 형성하는데 , 이 때 가중치를 그 SCC안..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [문제] [풀이] 만약 , 1번과 2번이 같은 팀이 된다면 능력치의 합은 S12+S21 = 5이다. 만약 , 1, 2, 3번이 같은 팀이 된다면 능력치의 합은 S12+S21+S23+S32+S13+S31 이다. 즉 , 완전탐색으로 모든 조합을 맞춰보면서 , 진행한 깊이(depth)가 한 팀(n/2) 만큼 진행했을 때, visit=true 인 팀의 시너지 총합을 A팀 이라 하고 , 이때 visit=false 인 팀의 시너..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net [문제] [풀이] 완전탐색 기초문제이다. 주어진 K 개의 숫자 중 6개만 뽑아서 모든 경우의 수를 만들어주면 된다. 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 30 31 32 33 34 35 36 37 38 39 import java.util.*; import java.io.*; import..

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 풀이 (1,1) 집에서 (m,n)학교 까지 가는데 최단거리로 가는 경우의 수를 구하는 문제이다. 우선 , 문제의 조건으로 오른쪽or아래 만 진행한다고 하였으니 어디로 가든 최단거리는 기본으로 잡고 들어간다. 만약 현지위치를 (x,y) 라고 하면 이 위치에 오기 까지의 경우의수는 (x-1,y) 또는 (x,y-1)의 합이다. 즉 , 현재위치의 경우의..

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 풀이 이전에 풀었던 컵라면 문제와 동일하다. https://katastrophe.tistory.com/73 1. 기간순으로 오름차순 정렬된 우선순위 큐(q1)에 삽입 2. 페이 순으로 오름차순 정렬된 우선순위 큐(q2)에 삽입 2_1. 삽입한 원소의 기간보다 q2의 사이즈가 더 크면 큐의 맨 앞의 원소를 poll. ( 더 적은 페이를 제거 ) 3. q2를 ..

https://www.acmicpc.net/problem/3977 3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 문제 풀이 이동 구간 경로가 주어 졌을 때 , 어느쪽을 스타트로 잡아야 하는지 정하는 문제다. 첫 번째 입력을 그래프로 나타내면 다음과 같은데 만약 3번에서 시작한다고 하면 주어진 경로를 모두 탐색할 수 없기 때문에 불가능. 그럼 나머지 0,1,2 번 지점에서는 저 중 아무곳에서 출발을 해도 모든 구간을 탐색이 가능하기 때문에 0,1,2 가 답. 즉 , { 0, 1, 2 } 를 하..

https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net [문제] [풀이] 어우 .. 어질어질하다.. SCC 활용 DP 문제이긴 한데 , 처음에 SCC 집단들을 구해서 indegree가 0인거부터 진행했는데 왜 안되지..? 했다가 나중에 알고보니 start 지점이 정해져있다는 걸 뒤늦게 알았고 한참을 헤맸다 .. 접근방법 1. SCC집단을 구할 것. 2. SCC집단마다 번호를 매기고 , 이 자체를 하나의 Node로 취급하여 또 다른 tot..