Oneulog

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이..

https://www.acmicpc.net/problem/4233 4233번: 가짜소수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 1에 대해서, ap == a (mod p)가 성립한다. 즉, a를 p제곱한 뒤, p로 나눴을 때, 나머지는 a가 되는 것이다. 하지만, p가 소수가 아닌 경우에 어떤 정수 a에 대해서 위의 식을 만족하는 경우가 있다. 이때, p를 밑이 a인 ..

https://www.acmicpc.net/problem/25827 25827번: 시간 구간 다중 업데이트 다중 합 시간 구간에 대한 질의를 처리하려고 한다. 전체 시간 구간은 [00:00:00,23:59:59]이다. h:m:s는 h시 m분 s초를 나타낸다. 전체 시간 구간은 길이가 1초인 구간으로 나누어져 있다. 즉, 전체 시간 구간은[0 www.acmicpc.net 문제 시간 구간에 대한 질의를 처리하려고 한다. 전체 시간 구간은 [00:00:00,23:59:59]이다. h:m:s는 h시 m분 s초를 나타낸다. 전체 시간 구간은 길이가 1초인 구간으로 나누어져 있다. 즉, 전체 시간 구간은[00:00:00,00:00:01], [00:00:01,00:00:02], ..., [23:59:58,23:59:..

https://www.acmicpc.net/problem/26646 26646번: 알프스 케이블카 ALPS 부원들은 친목 도모를 위해 다 같이 알프스 산맥으로 여행을 떠났다! 알프스 산맥은 $N$개의 산이 겹치거나 빈 부분 없이 일렬로 나열된 형태이며, 왼쪽에서부터 $i$번째에 위치한 산은 빗변 www.acmicpc.net 문제 ALPS 부원들은 친목 도모를 위해 다 같이 알프스 산맥으로 여행을 떠났다! 알프스 산맥은 N개의 산이 겹치거나 빈 부분 없이 일렬로 나열된 형태이며, 왼쪽에서부터 i번째에 위치한 산은 빗변을 아래로 하며 높이가 H_i인 직각 이등변 삼각형이다. ALPS 부원들은 체력이 좋지 않기 때문에 1번 산에서 시작해 N번 산에서 끝나는 케이블카 노선을 설치해 산을 오르려 한다. 노선을 설..

https://www.acmicpc.net/problem/14618 14618번: 총깡 총깡 입력의 첫 번째 줄에 전체 집의 수 N과 집과 집사이를 연결하는 도로 M이 공백으로 주어진다. (3 ≤ N ≤ 5,000, 3 ≤ M ≤ 20,000) 입력의 둘째 줄에 진서의 집 J가 주어진다 (1 ≤ J ≤ N) 입력의 셋째 줄 www.acmicpc.net 문제 동물 애호가 진서는 총깡총깡 뛰는 동물과 짝폴짝폴 뛰는 동물들을 K마리씩 키운다. 타지로 취업하게 된 진서는 내일 이사를 한다. 이사하게 될 집에서 같이 살게 될 룸메이트 일호는 동물을 싫어하기 때문에 진서는 근처의 집에 동물들을 한마리씩 맡길 예정이다. 진서가 동물들을 맡길 수 있는 집의 종류는 A형 집과 B형 집 2종류 이다. 우연하게도 짝폴짝폴 ..

https://www.acmicpc.net/problem/27977 27977번: 킥보드로 등교하기 첫 번째 줄에 학교까지의 거리, 킥보드 충전소의 개수, 최대 충전소 방문 횟수를 나타내는 세 정수 $L, N, K$가 공백으로 구분되어 주어진다. 두 번째 줄에 $i$번째 충전소의 위치를 나타내는 $N$개 www.acmicpc.net 문제 건덕이는 이번 학기 수강신청을 실패해 1교시 수업을 잔뜩 듣게 되었다! 건덕이의 등교 시간은 직장인의 출근 시간과 겹치는 시간대였기 때문에, 지하철을 타지 않고 킥보드를 구매해서 등교하기로 한다. 킥보드는 배터리 1을 소모해 거리 1만큼 이동할 수 있으며, 배터리를 모두 사용하면 킥보드가 멈추기 때문에 소진되기 전에 충전소에서 충전을 해야 한다. 건덕이의 집과 학교는 각..

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 문제 19학번 이준석은 학생이 N명인 학교에 입학을 했다. 준석이는 입학을 맞아 모든 학생과 친구가 되고 싶어한다. 하지만 준석이는 평생 컴퓨터랑만 대화를 하며 살아왔기 때문에 사람과 말을 하는 법을 모른다. 그런 준석이에게도 희망이 있다. 바로 친구비다! 학생 i에게 Ai만큼의 돈을 주면 그 학생은 1달간 친구가 되어준다! 준석..

https://www.acmicpc.net/problem/13270 13270번: 피보나치 치킨 KAIST 주변에서 먹을 수 있는 배달 음식들은 대부분 치킨이다. 이렇게 치킨집이 포화 상태지만 지훈이는 카이스트 주변에 새로 치킨집을 창업했는데, 생각보다 장사가 잘 되었다! 알고 보니 그가 www.acmicpc.net 문제 KAIST 주변에서 먹을 수 있는 배달 음식들은 대부분 치킨이다. 이렇게 치킨집이 포화 상태지만 지훈이는 카이스트 주변에 새로 치킨집을 창업했는데, 생각보다 장사가 잘 되었다! 알고 보니 그가 차린 치킨집의 신기한 방식 때문에 장사가 잘 된다고 한다. 지훈이의 치킨집에 치킨 주문을 하는 것은 간단하다. 어차피 지훈이네 치킨집의 메뉴는 도깨비오븐구이 하나이므로, 치킨 먹을 사람 수만 이야..