김머성 블로그

[BAE/<JOON> 문제풀이] 2109. 순회강연

https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 서론 문제 서술이 그리디 같이 생겨서 그리디인 줄 알았는데 입력 사이즈는 DP라서 DP로 풀었다. 특이하게도 제출하는데 메모리가 빡빡했다. + 제출하고 다른 사람 코드보는데 pq 였네.. 근데 pq면 그리디 맞구나. 풀이 직관적으로 생각했을 때 걸린 제한시간이 적은 곳 부터 순회하는게 맞다. 정렬 후 배열을 순회하며 강연한 수에 따라 버려지는 강연을 구해 최적값..

[BAE/<JOON> 문제풀이] 12931. 두배 더하기

https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 서론 그리디 문제 풀이 각 자리마다 1씩 더하면 경우의 수가 너무 많아진다. 0 배열에서 시작하는게 아닌 입력 배열에서 거꾸로 2씩 나눠가며 각 자리마다 나오는 나머지의 합을 거리 비용으로 계산하여 TLE를 피할 수 있다. 2로 나누는 비용과 1을 빼는 비용은 같으므로 항상 이 경우가 최적일 수 밖에 없다. 최적이 아니려면 2로 나누는 비용이 따로 주어져 2로 나누는 것 보다 1씩..

[BAE/<JOON> 문제풀이] 5427. 불

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 서론 풀이 좀 그때 그때 풀자마자 써야겠다. 귀찮아서 나중에 몰아쓰니까 문제 2번푸는 기분이다. 풀이 불이 사람보다 먼저 퍼진다는게 가장 중요하다. 그래서 처음에 작성한 pq를 사용하는 풀이는 폐기했다. pq로는 불과 사람을 번갈아 움직이는 구현이 힘들다. 그 외에는 그냥 불 움직이고 사람 움직이고 반복하며 동일한 타일에서 겹치지 않도록만 신경쓰면 된다. 쉬운 문젠 줄 알았는데 움직이는 순서 짜는 것 때문에 ..

[BAE/<JOON> 문제풀이] 1139. 울타리

https://www.acmicpc.net/problem/1139 1139번: 울타리 $A \le B \le C$를 만족하는 $A$, $B$, $C$는 $A+B>C$를 만족할 때만 울타리를 만들 수 있다. 그리고, 그 때 넓이는 $\sqrt{p(p-A)(p-B)(p-C)}$이다. 여기서 $p=(A+B+C)/2$ 이다. www.acmicpc.net 서론 N 이 10 초반 ~ 10 후반 인 문제는 대부분 비트마스크 문제였던 것 같다. 풀이 각각의 울타리 사용 여부를 비트에 대응시키고 아직 확인하지 않은 상태일 때만 검사를 진행하면 된다. 한번에 3개씩 묶어서 조작해야하니까 구현이 살짝 복잡하긴 하다. 코드 더보기 #include using namespace std; using ll = long long; s..

[BAE/<JOON> 문제풀이] 2234. 성곽

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 서론 Flood-Fill BFS 문제 풀이 이 문제는 특이하게 cell 마다 4개의 벽이 있을 수 있고 벽의 상태를 2진수로 저장했다. 총 3가지를 구해야 한다. 1. 방의 개수 = BFS 2. 가장 넓은 방의 넓이 = BFS 3. 하나의 벽을 제거해 얻을 수 있는 가장 넓은 방의 크기 = 인접한 2개의 방의 합의 최대 크기 3번은 각 방에 해당하는 cell들을 배열로 저장한 뒤 순회하며 어..

[BAE/<JOON> 문제풀이] 4196. 도미노

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 서론 SCC + 토폴로지 소트? 문제 SCC끼리 진입 간선 개수가 0인 SCC의 개수를 세면 된다. 풀이 처음에는 단순히 진입 간선이 0인 정점을 세는 문젠 줄 알았는데 도미노 배열에서 순환이 있어도 반드시 1개는 쓰러트려야 전체가 쓰러지므로 SCC 문제였다. 별도의 직관이나 추론 없이 알고리즘 원형만 사용해도 풀리는 문제라 풀이 과정에 딱히 쓸게 없다. 코드 더보기 #include using namespace ..