본문 바로가기

전체 글210

[BOJ] 17404 : RGB거리 2 문제 링크 17404번: RGB거리 2 (acmicpc.net) 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 유명한 DP문제인 RGB거리의 변형 문제 1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 기존의 RG.. 2022. 3. 22.

[BOJ] 19539 : 사과나무 문제 링크 19539번: 사과나무 (acmicpc.net) 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 난이도가 골드였어도 이상하지 않았을 문제. 풀이 처음에는 직접 모든 나무에 물을 주면서 YES or NO를 판단했다. 나무의 높이를 저장한 후 나무의 높이를 2또는 1을 깎으면서 모두 0이 될 수 있는지를 체크하려 했다. 하지만 이렇게 하면 나무를 3만큼 키우는게 맞는지 2만큼 키우는게 맞는지 1만큼 키우는게 맞는지 판단하기가 애매했다. 1. 하루에 무조건 합쳐서 3의 높이를 키워야하기 때문에 모든 나무의 높이의 합이 3의 배수가 아니라면 무조건 ".. 2022. 3. 22.

[BOJ] 15823 : 카드 팩 구매하기 문제 링크 15823번: 카드 팩 구매하기 (acmicpc.net) 15823번: 카드 팩 구매하기 첫 줄에는 두 개의 자연수 N과 M이 공백으로 구분되어 주어진다. N은 상점에 진열된 카드의 수이며 M은 주띵이가 구매해야 할 카드 팩의 수다. 이후 두 번째 줄에는 총 N개의 나열된 카드에 대한 www.acmicpc.net 포인트 잡기는 쉬웠지만 구현이 어려웠던 문제. 풀이 과정 카드 팩을 구성하는 카드의 수를 Mid 로 두고 이분 탐색을 통해 최대 카드의 개수를 구한다. 카드가 총 N개가 있을 때 M개의 카드팩을 만들어야 한다면 한 카드팩에는 최대 N/M 개의 카드가 들어갈 수 있다. L = 1 , R = N/M 으로 두고 while(L = M) // L = mid + 1; else R = mid - .. 2022. 3. 21.

[BOJ] 1700 : 멀티탭 스케줄링 문제 링크 1700번: 멀티탭 스케줄링 (acmicpc.net) 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 알고리즘 분류가 순수하게 그리디 알고리즘인 문제. 풀이 너무 과하게 생각해서 오래걸렸던 문제. 멀티탭을 최소한으로 뽑으면서 모든 전기용품을 사용할 수 있게 계획하는 문제이다. 처음에 나는 이미 멀티탭에 꽂혀있는 장치 중 앞으로 사용할 횟수가 많은 것은 뽑지 말아야겠다고 생각했다. 앞으로 쓸 일이 많다면 꽂아두는게 이득이라고 판단했기 때문이다. 그래서 이미 꽃혀있는 장치 중 앞으로 쓰일 횟수가 가장 .. 2022. 3. 17.

[BOJ] 10775 : 공항 문제 링크 10775번: 공항 (acmicpc.net) 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 그리디 알고리즘을 이용해서 푸는 문제 풀이 과정 보통 그리디 알고리즘 문제들을 보면 무엇을 기준으로 우선순위를 정할지 쉽게 정할 수 없는 문제들이 많지만, 이 문제는 명확했다. i번째 비행기는 1 G >> P; memset(section, -1, sizeof(section)); int ans = 0; for (int i = 1; i > num; int idx = 0; if (.. 2022. 3. 16.

[BOJ] 13308 : 주유소 문제 링크 13308번: 주유소 (acmicpc.net) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net DP와 그래프탐색 중 다익스트라 알고리즘이 결합된 문제. 사실 DP보다는 다익스트라 알고리즘에 가까운 것같다. 풀이 처음에 원래 다익스트라 알고리즘 처럼 dist라는 1차원 배열을 만들어서 최소비용을 저장했다. 하지만 이렇게 되면 예제처럼 이러한 상황에서 dist[3] 에는 1->3 경로로 인해 15가 저장되어있고, 1 -> 2 -> 3 -> 4 로 가는 루트가 최소비용으로 4에 도.. 2022. 3. 15.

[BOJ] 10272 : 현상금 사냥꾼 김정은 문제 링크 10272번: 현상금 사냥꾼 김정은 (acmicpc.net) 10272번: 현상금 사냥꾼 김정은 현상금 사냥꾼인 정은이는 지금 범죄자를 쫓고 있는 중이다. 정은이는 갈치 II호를 사용해서 우주를 돌아다니면서 조사를 하는데, 2차원 유클리드 우주에 존재하는 N개의 다른 행성을 모두 방문 www.acmicpc.net 풀이 내가 감히 풀 수 없을 정도로 어려웠던 DP 문제. 정은이는 왼쪽에서 오른쪽으로 갈 떄는 X좌표가 오름차순이 되도록 행성을 방문하고, 반대로 오른쪽에서 왼쪽으로 갈 때는 X좌표가 내림차순이 되도록 방문해야한다. 또한 최소한의 거리로 행성을 모두 방문해야한다. 최소한의 거리로 모든 행성을 방문해야하기 때문에 같은 행성을 두 번 방문하는 경우는 없다! 무조건 제일 끝 행성을 찍고 출.. 2022. 3. 11.

[BOJ] 2842 : 집배원 한상덕 문제 링크 2842번: 집배원 한상덕 (acmicpc.net) 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 투포인터와 BFS가 합쳐진 재밌는 문제였다. 참고 링크 https://dar0m.tistory.com/77 [C++] vector 배열 중복 제거 하는 법 배열 중복을 제거하는 법 vector v 를 유일한 원소들의 집합으로 만들고 싶다면, 정렬을 한다. : sort 연속된 중복 원소를 vector의 제일 뒷부분(쓰레기 값)으로 보내버린다. : unique 중복된 원소들 dar0m... 2022. 3. 10.

[BOJ] 3197 : 백조의 호수 문제 링크 3197번: 백조의 호수 (acmicpc.net) 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 빙판에 막혀 서로 만날 수 없는 두 백조가 빙판이 녹아 만나기 위해선 며칠이 걸리는지 출력하는 문제. '.'은 물, 'X'는 빙판 'L'은 백조를 나타낸다. 물과 인접한 빙판은 하루에 걸쳐 녹는다. 풀이 처음에 문제를 제대로 안 읽어서 두 백조가 최단거리로 만나기 위해 필요한 날을 출력하는 것인 줄 알았다. 그래서 한참을 헛고생하다가 알고리즘 분류가 다익스트라가 아닌 것을 .. 2022. 3. 8.

이전 1 ··· 17 18 19 20 21 22 23 24 다음

티스토리툴바