본문 바로가기

백준/Platinum10

[BOJ] 23289 : 온풍기 안녕! 문제 링크 23289번: 온풍기 안녕! (acmicpc.net) 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 온풍기를 이용해서 조사하는 칸의 온도가 모두 특정 온도 이상이 되도록 하는데 테스트 과정을 몇 번 거쳐야하는지 계산하는 구현 문제. 여기서는 테스트 과정 한 번을 초콜릿을 하나 먹는 것으로 표현했다. 풀이 R x C 크기의 격자에 온풍기가 놓여있다. 이 온풍기에서 바람이 한 번 나오면 문제에서 제시된 그림대로 격자 칸의 온도가 상승하게 된다. 성능 테스트의 과정은 다음과 같다. 1. 집에 있는 모든 .. 2022. 6. 9.

[BOJ] 5373 : 큐빙 문제 링크 https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net 큐브 돌리는 것을 구현하는 구현문제. 풀이 정말 그냥 노가다로 큐브를 돌릴때마다 6면의 변화를 구현하는 구현문제이다. 큐브를 한 번 돌리면 돌릴 때 바라보고있는 면의 반대쪽 면을 제외한 5면은 회전 후 구성이 바뀐다. 바라보고 있는 면은 돌리는 방향에 따라 시계방향 또는 반시계 방향으로 큐브가 바뀔 것이고, 바라보고 있는 면과 접하는 4개의 면은 9칸 중 3칸이 회전한다. 큐브를 돌리면 .. 2022. 5. 16.

[BOJ] 10251 : 운전 면허 시험 문제 링크 10251번: 운전 면허 시험 (acmicpc.net) 10251번: 운전 면허 시험 만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다. www.acmicpc.net 풀이 처음에는 그래프 탐색으로 풀어보려고 했다. 보통 그래프탐색은 상하좌우로 탐색하지만 이건 특별하게 오른쪽, 아래로만 탐색하는 그래프 탐색인 줄 알았다. 그래서 우선순위 큐를 만들어서 DP배열에 기름의 양과, 걸린시간을 모두 저장한다.탐색도중 기름의 양이 G를 넘어가면 그 경로로는 더이상 탐색을 하지 않는다. 이렇게 하려했더니 우선순위 큐에 들어가야 할 정보들이 너무 많았다 1. 좌표, 2. 기름의 총량, 3. 걸린 시간, 4. 방향 을 저장해.. 2022. 3. 25.

[BOJ] 1028 : 다이아몬드 광산 문제 링크 1028번: 다이아몬드 광산 (acmicpc.net) 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net 가장 큰 다이아몬드의 크기를 출력하는 문제. size 1: size 2: size 3: 1 1 1 1 1 1 1 1 1 1 1 1 1 다이아몬드의 형태는 이러하다. 풀이 문제 분류가 DP 인것을 보고 처음엔 의아했다. 차라리 분할정복문제면 몰라도 이걸 어떻게 DP로 푸는 지 도저히 감이 잡히지 않았다. 구글 속 선배님들의 힌트를 받아서 풀었다. DP배열에 왼쪽 아래로 최대 대각선의 길이, 오른쪽 아래로 최대 대각선의 길이를 저장하는 것이었다. L.. 2022. 3. 23.

[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.

[BOJ] 1328 : 고층 빌딩 문제 링크 1328번: 고층 빌딩 (acmicpc.net) 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 왼쪽에서 본 빌딩의 개수와 오른쪽에 본 빌딩의 개수가 주어졌을 때 가능한 빌딩 배치의 경우의 수를 구하는 문제. 참고 링크 https://beginthread.tistory.com/151 [ BOJ 백준 1328번 - 고층 빌딩 ] 해설 및 코드 https://www.acmicpc.net/problem/1328 목적 빌딩의 개수 N, 가장 왼쪽 또는 오른쪽에서 봤을 때 보이는 빌딩의 수 L과 R이 주어졌.. 2022. 3. 7.

이전 1 2 다음

티스토리툴바