문제 노트 (155) 썸네일형 리스트형 트럭( BOJ 13335 ) 문제 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 문제 파악하기 N개의 트럭이 다리를 건너는데 필요한 최소 시간을 구하는 문제입니다. 트럭의 순서는 바꿀 수 없으며, 모든 트럭은 다리를 건너는데 W만큼의 시간이 걸립니다. 최대 하중인 L을 넘지 않는 선에서 모든 트럭이 다리를 건너는데 필요한 최소 시간을 구하기 위해서는 현재 다리를 건너고 있는 트럭의 총 하중을 고려하여 직접 시뮬레이션 할.. 보안 업체( BOJ 9938 ) 문제 : https://www.acmicpc.net/problem/4243 4243번: 보안 업체 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 상점의 수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 시작점의 위치 a (1 ≤ a ≤ N)가 주어진다. a번째 점, pa = s가 시 www.acmicpc.net 문제 파악하기 N개의 상점을 순찰하는데 걸리는 대기 시간의 최솟값을 구하는 문제입니다. 문제를 해결하기 위해 우리는 시작점부터 왼쪽 혹은 오른쪽에 위치한 상점을 하나씩 선택하여 방문할 수 있으며, 이 과정에서 상점들이 가지게 되는 대기 시간을 구하고 비교하면 정답을 구할 수 있습니다. 사실 오른쪽과 왼쪽에 위치한 상점 중 하나를 방문하는 알고리즘은 전형적인.. 소가 길을 건너간 이유( BOJ 14469 ) 문제 : https://www.acmicpc.net/problem/14469 14469번: 소가 길을 건너간 이유 3 첫 번째 소는 2초에 도착하고 3초에 농장을 입장한다. 그 다음에는 세 번째 소가 5초에 도착하여 12초에 농장을 입장한다. 마지막으로 두 번째 소가 8초에 오는데, 세 번째 소가 검문을 받고 있으 www.acmicpc.net 문제 파악하기 N마리의 소가 농장에 도착해서 검문을 완료하기까지 걸리는 최소 시간을 구하는 문제입니다. N마리 소에 대한 2가지 정보(도착 시간, 검문시간)를 이해하면 문제는 어렵지 않게 해결할 수 있습니다. 문제 해결하기 우선 도착 시간은 소가 검문을 할 수 있는 시간을 의미합니다. 따라서, 우리는 소들을 도착한 시간을 기준으로 정렬하면 대략적인 순서를 정할 수 .. 점( BOJ 2541 ) 문제 : https://www.acmicpc.net/problem/2541 2541번: 점 첫째 줄에는 처음에 S에 속하는 점 (a, b)의 좌표인 두 자연수 a와 b가 하나의 공백을 두고 순서대로 주어진다. 그리고 그 다음 다섯 줄에는 각 줄마다 한 개의 점 (p, q)의 두 자연수 p와 q가 하나의 www.acmicpc.net 문제 파악하기 시작점 (a, b)에서 3가지 규칙을 사용하여 집합 S에 점을 추가할 때, 주어진 (x, y)가 집합 S에 포함될 수 있는지 여부를 확인하는 문제입니다. 입력되는 점의 범위는 1 ~ 100,000이기 때문에 단순히 모든 경우의 수를 파악할 수는 없습니다. 대신 규칙을 계속 적용할 때 나타나는 특징을 살펴보면 문제를 해결할 수 있습니다. 문제 해결하기 규칙 3가지를.. What's Up With Gravity( BOJ 5827 ) 문제 : https://www.acmicpc.net/problem/5827 5827번: What's Up With Gravity Output Details The captain starts at position (4, 2). She flips gravity and falls to position (2, 2) and then moves right twice to arrive at (2, 4). She flips gravity again and falls to position (4, 4) and then moves right once to position (4, 5). Finally www.acmicpc.net 문제 파악하기 N*M 형태의 2차원 맵에서 C 위치에 있는 캡틴 Bovidian가 목적지 D까지 .. 트리와 쿼리( BOJ 25402 ) 문제 : https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 문제 파악하기 집합 S에 포함된 정점들이 몇 개씩 연결되었는지 판단하는 문제입니다. 문제에서 요구하는 연결 강도는 결국 연결된 정점 중 2개의 정점을 고를 수 있는 경우의 수를 의미하며, 만약 t개의 정점이 연결되어 있다면 연결 강도는 t*(t-1)/2 로 계산됩니다. 따라서, 문제를 해결하기 위해서는 몇 개의 정점들이 현재 연결되어 있는지 확인해야 합니다. 다만, 모든 경우를 .. Contact( BOJ 1013 ) 문제 : https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 문제 파악하기 주어진 N개의 문자열이 각각 (100+1+ | 01)+ 을 만족하는지 확인하는 문제입니다. 라이브러리 함수를 사용하거나 오토마타를 사용하는 방법도 있지만, 여기에서는 반복문과 문자열만을 사용하여 문제를 해결해보겠습니다. 문제 해결하기 문자열을 탐색할 때에는 현재 어떤 문자열 형식을 확인하고 있는지 파악하는 것이 중요합니다. 우리는 "100+1+" 형식과 "01" .. 커다란 도시( BOJ 25380 ) 문제 : https://www.acmicpc.net/problem/25380 25380번: 커다란 도시 KOI시는 너무나 커다라서, 이동하려면 시간이 오래 걸린다. 그래서 KOI시는 도시를 관통하는 아주 긴 도로를 건설하였다. 도로는 남북 방향 또는 동서 방향으로 무한히 뻗어 나간다. 남북 방향의 www.acmicpc.net 문제 파악하기 K명의 경찰이 서로를 만나기 위해 필요한 이동거리의 합의 최솟값을 구하는 문제입니다. 경찰들은 주어진 길을 통해서만 움직일 수 있기에 모든 경로가 최단 경로(맨해튼 경로)가 아닐 수 있습니다. 그렇다고 한 명씩 확인하기에는 최대 200,000명의 경찰 사이의 경로를 확인해야 하기에 제한시간 이내에는 불가능합니다. 이렇게 복잡한 문제는 단계를 나눠서 생각하면 알고리즘을 .. 이전 1 2 3 4 5 6 ··· 20 다음