본문 바로가기

분류 전체보기140

[백준] 16678 - 모독 https://www.acmicpc.net/problem/16678 16678번: 모독 명예에 죽고 명예에 사는 나라 얼라이언스에는 1명의 왕과 N명의 국회의원이 있다. 각 N 명의 국회의원은 a1, a2, ..., aN 의 명예 점수를 갖고 있으며, 명예 점수가 양수인 한 그들은 국회의원을 www.acmicpc.net 처음에 각 입력에 대해 중복이 없는 줄 알고 풀었다가 반례를 찾아서 다시 수정했다. 문제를 잘 읽어보면, "Defile" 한 번으로 모든 국회의원을 박탈시키려면, 모든 국회의원의 명예 점수가 연속되어야 한다. 당연히 중간에 중복이 있을 수 있다. 그렇다면 우리가 해야할 일은 입력을 연속되게 만들어야 한다. 그러기 위해서는 먼저 정렬을 진행하자. 다음 예제로 살펴보자. 7 5 5 3 1 3.. 2023. 6. 20.
[백준] 2831 - 댄스 파티 https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 문제를 살펴보면, 각 성별의 입력은 반대 성별의 입력의 반대 부호와만 연결될 수 있다. 그렇다면 각 성별을 어떻게 연결할지 살펴보자. 만약 음수 부호의 남자를 연결하려고 할 때, 여자는 양수 부호에다가 abs(남자) > 여자 여야 한다. 그렇다면 어떤 순서로 연결해야 할까? 만약 남자의 입력이 -100 -200 -300 이고, 여자의 입력이 110 210 310 이라면 당연히 3개의 쌍을 만들.. 2023. 6. 20.
[백준] 16500 - 문자열 판별 https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net 이 문제는 처음 봤을 때는 완전 탐색 문제일 줄 알았다. 하지만 다음과 같은 입력이 들어온다면? aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(a가 홀수개) 8 aa aaaa aaaaaa aaaaaaaaaa aaaaaaaaaaaa aaaaaaaa.. 2023. 6. 20.
[백준] 1765 - 닭싸움 팀 정하기 https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 문제의 이해를 정말 잘해야 하는 문제이다. 보통의 친구 관계 문제에서는 한 연결 요소에서 관계가 "친구" 인지 "원수" 인지만 존재한다. 그래서 이 문제도 처음에 한 연결 요소 내에서 친구와 원수가 존재하는지만 판단하려고 했다. 하지만 이 문제에서 F 1 2 E 2 3 E 3 4 이런 관계에서는 1과 3이 원수관계 같지만, 사실 아무 관계도 아니다. 따라서 이 입력에서는 (1, 2, 4) (3) 이라는 팀이 만들어진다. 즉, 문제에 나와있는 "친구의 친구는 친구"와 "원.. 2023. 6. 20.
[백준] 16400 - 소수 화폐 https://www.acmicpc.net/problem/16400 16400번: 소수 화폐 구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다. www.acmicpc.net 에라토스 테네스의 체 + dp 문제였다. 먼저 화폐의 종류를 구하기 위해 에라토스 테네스의 체로 N 이하의 소수를 걸러내자. 인접 리스트를 활용해 N 이하의 모든 소수를 담고, 해당 소수들로 지불할 수 있는 방법의 수를 dp로 구하면 된다. #include #include #include using namespace std; int a[40001], dp[40001]; vector prime; int main() { int n; cin >> n; for (int i = 2; i * i 2023. 2. 14.
[백준] 2022 - 사다리 https://www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 기하학이 가미된 이분 탐색 문제였다. 그림이 좀 이상하지만, x와 y가 만나는 교점과 mid의 양 끝점을 세 점으로 하는 삼각형의 넓이를 살펴보자. 우리는 mid값을 구하기 위해 파라매트릭 서치로 이분 탐색을 사용할 것이고, 매 반복마다 mid 값으로 A, B값을 구할 수 있을 것이다(via 피타고라스 정리). 한 편 빨간색 삼각형의 넓이 S = c * mid / 2 이다. 이 삼각형의 넓이를 A, B, c로도 구할 수 있다. .. 2023. 2. 14.
[백준] 2982 - 국왕의 방문 https://www.acmicpc.net/problem/2982 2982번: 국왕의 방문 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안 www.acmicpc.net 주어지는 고둘라가 지나가는 시간에 들리는 경로를 제외한 최단 거리를 구하는 문제이다. 그래서 고둘라가 지나가는 경로의 지나가는 시간을, pair go[1001][1001]로 정해주었다. 따라서 pair go[i][j]는 고둘라가 i에서 j까지 이동할 때, first = 출발하는 시간, second = 도착하는 시간으로 하였다. 이 부분까지는 쉽게 할 수 있다. 그렇다면 상근이가 배달할 때는 어떤 점을 .. 2023. 1. 22.
[백준] 2307 - 도로검문 https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 이 문제에서 모든 M개의 간선에 대해 제외하고 다익스트라를 돌리게 되면, O(MNlogM) -> TLE가 날 수 있다. 따라서 시간 최적화를 진행해야 한다. 잘 생각해 보면, 용의자가 1번 정점에서 n번 정점까지 가는 데에 쓰인 간선 중에서만 검문을 거치면 된다. 그 외 간선에서는 검문을 해봤자, 최단 거리에 영향을 주지 않기 때문이다. 그렇다면 최단 거리에 쓰인 간선을 어떻게 판단할 수 있을까? 본인은.. 2023. 1. 21.
[백준] 4315 - 나무 위의 구슬 https://www.acmicpc.net/problem/4315 4315번: 나무 위의 구슬 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n이 주어지며, n은 정점의 개수이다. 다음 n개 줄에는 각 정점의 정보가 주어진다. 첫 번째 숫자는 정점의 번 www.acmicpc.net 문제를 요약하면 어떤 정점들에 여러 개의 구슬이 있을 때, 적당히 배분하여 모든 정점에 구슬이 딱 1개만 존재하도록 하는 것이다. 이 문제의 핵심은 바로 "리프 노드부터 구슬을 채워나간다"는 것이다. 따라서 dfs로 리프노드부터 탐색해 부모 노드와 현재 노드의 구슬의 차이만큼 구슬의 상태를 변화하고, 이 차이의 절댓값만큼 답을 더해주면 된다. 사실 코드는 굉장히 간단하지만 리프 노드부터 채워.. 2023. 1. 17.

티스토리툴바