본문 바로가기

분류 전체보기140

[백준] 13911 - 집 구하기 https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 간략하게 요약하면 임의의 정점에서 서로 다른 두 정점까지의 거리의 최솟값을 구하는 문제이다. 모든 맥도날드와 스타벅스 정점에서 다익스트라를 실행하면 TLE가 나기 때문에 다른 방법을 구사해야 한다. 핵심은 다음과 같다. 맥도날드에 이어진 가상의 정점과, 스타벅스에 이어진 가상의 정점을 생성하고 가중치가 0인 간선으로 연결하는 것이다. 이 예제에.. 2022. 11. 8.
[백준] 15565 - 귀여운 라이언 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net K와 N 모두 1 이상 10^6 이하인 구간이므로, 일반적인 투 포인터를 사용하면 TLE가 날 수 있다. 그래서 라이언 인형의 좌표만 따로 저장하였다. 예를 들어 예제 입력 1에서 1 2 2 2 1 2 1 2 2 1 => 0 4 6 9 이런 식으로 라이언의 좌표만 따로 저장하면 O(N) 시간에 답을 구할 수 있는 것이 자명하다. 이후 left = 0, right = k - 1로 두고 탐색하면.. 2022. 11. 5.
[백준] 14400 - 편의점 2 https://www.acmicpc.net/problem/14400 14400번: 편의점 2 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고 www.acmicpc.net 2차원 평면 상의 점들과의 거리 중 가장 짧은 거리에 있는 좌표를 구하는 문제이다. 그리디 하게 접근하면, 해답은 다음과 같다. x = 주어진 점들 중에서 x좌표의 중간점 y = 주어진 점들 중에서 y좌표의 중간점 여기서 중간점이라는 것은 평균이 아니라, n / 2번째에 있는 점의 좌표라는 것이다. 따라서 다음과 같이 구현할 수 있다. #include #include #include using na.. 2022. 11. 5.
[백준] 20665 - 독서실 거리두기 https://www.acmicpc.net/problem/20665 20665번: 독서실 거리두기 첫 번째 줄에 독서실 좌석의 개수 N, 독서실 예약자 수 T, 민규가 좋아하는 좌석 번호 P 가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100, 1 ≤ T ≤ 500, 1 ≤ P ≤ N) 다음 T 개의 줄에는 독서실 입실 www.acmicpc.net 아주 최적의 그럴듯한 방법이 있을 것 같지만 사실 시간(분 단위)의 범위가 1440분이라 단순 구현 + 시뮬레이션을 진행하면 된다. 입력을 받고, 시작 시간 기준 오름차순, 끝나는 시간 기준 오름차순으로 정렬한다. 손님을 정렬된 순서에 따라 탐색하며 앉을 수 있는 좌석의 번호를 구한다. 모든 좌석을 탐색하며 앉을 수 있는 좌석 중에 가장 가까이에 있는 사람.. 2022. 11. 4.
[백준] 1368 - 물대기 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 처음부터 우물이 파져 있는 것이 아니기 때문에, 약간 까다로운 문제였다. 우물을 파는 방법, 물을 끌어오는 방법 2개가 존재하기 때문에 2가지 방법을 통일하기 위해 가상의 0번째 노드를 추가하였다. 그래서 우물을 파는 방법을 0번째 노드와 연결시켜서, MST를 구현하면 된다. #include #include #include using namespace std; int.. 2022. 9. 21.
[백준] 21317 - 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 매우 큰 점프는 1번 이하로 사용할 수 있기 때문에, dp[i][0] = 매우 큰 점프를 사용하지 않았을 때 i번째 돌에 올 수 있는 최소 에너지 dp[i][1] = 매우 큰 점프를 사용한 후 i번째 돌에 올 수 있는 최소 에너지 로 정의하고 구현하였다. 매우 큰 점프는 2개의 돌을 건너뛰어 이동하므로 dp[2][0] = a[1].first; dp[3][0] = min(a[1].second, a[1].first + a[2].first); 이다. #include using namespace std; int n, k, dp[3.. 2022. 9. 21.
[백준] 1188 - 음식 평론가 https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 모든 음식 평론가가 받는 소시지의 길이는 N / M으로 같다. 그렇다면 처음 모든 소시지를 1열로 나열해보자. 최대 M - 1번으로 자르면 M명의 평론가에게 나누어 줄 수 있다. 하지만 N = 4, M = 6인 경우에는 4번만 잘라도 6명의 평론가에게 나누어 줄 수 있게 된다. N = 4, M = 6인 경우에는 2개의 소시지에 3명씩 배분하는 경우의 수를 두배 하면 된다. N = 6, M = 9인 경우에는 2개의 소시지에 3명씩 배분하는 경우의 수를 세배하면 된다. 결국, 답은 M - GCD(N, M.. 2022. 9. 21.
[백준] 20207 - 달력 https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 주어지는 일정을 어떻게 저장하고 관리하는지가 관건인 문제였다. 먼저 주어지는 조건에 맞게 입력을 정렬한 후, day라는 1차원 배열에 시작~끝 구간만큼 1씩 증가시켜준다. 만약 어떤 날의 day 배열 값이 3이라면 해당 일자에는 3개의 일정이 중복되어있다는 뜻이므로, 해당 일자의 직사각형의 높이는 3이 된다. 만약 어떤 날의 day 배열 값이 0이라면 해당 일자에는 일정이 없고, 이전까지 나왔던 일정의 직사각.. 2022. 9. 19.
[백준] 20437 - 문자열 게임 2 https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 문자열이 주어지고, 주어진 조건 2개에 맞는 sub string을 구하는 문제이다. 언뜻 보면 굉장히 다른 두 개의 조건 같지만, 실은 같은 구조의 조건이다. 바로 첫 번째, 마지막 글자가 같고 어떤 문자를 정확히 k개 포함하는 문자열이라는 것이다. 첫 번째 조건의 문자열도 위 문장을 적용시킬 수 있다. 그렇다면 조건에 맞는 문자열을 구하는 과정을 보자. 먼저 주어지는 문자열을 이용해서 각 알.. 2022. 9. 19.

티스토리툴바