Today I Learned

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net [조건] 시간제한 : 1초 메모리 제한 : 128MB [문제 조건] 맥주 한 박스에는 맥주가 20개 들어있다. 한 병을 마시면 50미터를 갈 수 있다. 편의점에 들렸을 때 빈 병을 버리고 새 맥주 병을 살 수 있다. 맥주는 총 20개까지 가질 수 있다. [목표] 집에서 페스티벌에 도착할 수 있다면 "happy", 도착할 수 없다면 "sad"를 출력한다. [접근 방식] 한 노드에서 다른 노드로..

https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [조건] 시간제한 : 1초 메모리 제한 : 256MB [문제 조건] 무게가 서로 다른 N개의 물건이 주어진다. 각 물건은 1부터 N까지 번호가 부여된다. 물건들의 무게 비교가 M개 주어진다. 1 3 이라면 1번 물건이 3번 물건보다 무겁다는 뜻이다. [목표] 1번부터 N번까지 차례대로 비교 결과를 알 수 없는 물건의 개수를 출력한다. [접근 방식] 그래프 문제와 비슷하다고..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net [조건] 시간제한 : 2초 메모리 제한 : 128MB [문제 조건] 전구들의 상태 2개가 주어진다. (각 A, B) 각 전구는 켜져있는 상태와 꺼져있는 상태 중 하나의 상태를 가진다. (0, 1로 표시) 1번 전구의 스위치를 누르면 1, 2번 전구의 상태가 바뀐다. N번 전구의 스위치를 누르면 N - 1, N번 전구의 상태가 바뀐다. n번 전구의 스위치를 누르면 n -..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net [조건] 시간제한 : 2초 메모리 제한 : 512MB [문제 조건] 학생 i에게 A만큼의 돈을 주면 친구가 된다. 친구의 친구는 나의 친구이다. [목표] 모든 학생을 준석이의 친구로 만드는데 드는 최소비용을 구한다. 모든 학생을 친구로 만들 수 없다면 "Oh no"를 출력한다. [접근 방식] 유니온 파인드를 활용한다. 유니온 과정..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net [조건] 시간제한 : 1초 메모리 제한 : 256MB [문제 조건] 용액의 종류는 산성 용액과 알칼리성 용액, 총 2가지의 용액이 있다. 산성 용액의 특성값은 1부터 1,000,000,000까지이다. 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지이다. [목표] 세 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 세 용액의 특성값을..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net [조건] 시간제한 : 2초 메모리 제한 : 128MB [문제 조건 리마인드] 화물(박스)이 M개가 있다. (1

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net [조건] 시간제한 : 12초 메모리 제한: 1024MB [완전 탐색] 크기가 같은 서로 다른 4개의 배열을 완전 탐색하면 문제를 풀 수 있다고 생각했다. 하지만 문제 조건 중 N은 최대 4,000이므로 O(N^4)는 12초가 부족함을 알 수 있었다. [2개씩 묶기] 서로 다른 4개의 배열을 각 2개씩 묶어 생각해보았다. A와 B, C와 D로 묶어 생각해본다면 A와 B에서 나올 수..