전체 글 (21) 썸네일형 리스트형 BOJ 15972 : 물탱크 문제 링크 : https://www.acmicpc.net/problem/15972 15972번: 물탱크 세로 길이가 N, 가로 길이가 M, 높이가 H인 물탱크가 있다. N, M, H는 모두 양의 정수이다. 은 세로 길이가 2, 가로 길이가 3, 높이가 5인 물탱크 모양을 보여준다. 에서 보듯이 물탱크 www.acmicpc.net 우선순위큐와 BFS를 이용한 문제입니다. 결론적으로 물이 마지막에 빠져나가는 구멍은 바깥과 연결된 구멍일 것입니다. 따라서, 역으로 바깥과 연결된 구멍이 있는 칸부터 우선순위큐에 저장합니다. 우선순위큐에서는 {물의 높이, 칸의 x 좌표, 칸의 y 좌표}를 저장하며 물의 높이에 따라 오름차순으로 정렬됩니다. 이후 우선순위큐에서 BFS를 돌리는 과정에서 관찰이 필요합니다. 현재 칸과.. Codeforce Round #771 (Div. 2) 풀이 대회 링크 : https://codeforces.com/contest/1638 A번 문제 : Reverse 순열을 한번만 뒤집어 사전순으로 가장 빠르게 만들어야 하는 문제입니다. 순열과 사전순이라는 특성을 이용하여 입력받은 순열을 순차탐색하면서 \(p[i] != i\) 인 최초의 지점을 찾고 \(i\)를 값으로 가지는 순열의 위치를 찾아 두 개의 지점을 양 끝점으로 하여 reverse 연산을 해주면 사전순으로 가장 빠른 순열을 만들어줄 수 있습니다. #include using namespace std; typedef long long ll; int t, n, p[505]; int main() { scanf("%d", &t); while(t--) { scanf("%d", &n); int fir = 0; /.. USACO 2021 December Silver 풀이 https://www.acmicpc.net/category/612 USACO 2021 December Contest www.acmicpc.net UPD : USACO 2021 December Silver 1번 문제 풀이를 Silver 2, 3번을 추가하여 Silver 풀이로 업데이트 하였습니다. 1번 문제 : Closest Cow Wins 입력받는 patch의 위치와 Nhoj의 소들의 위치를 하나의 배열로 만듭니다. 오름차순으로 배열을 정렬하여 순차탐색하면서 patch의 값을 더해주다가 Nhoj의 소가 등장한다면 값을 우선순위큐에 저장하는 방식으로 해결할 수 있습니다. 다만, 두 마리의 Nhoj 소들 사이에 존재하는 patch가 여러개라면 이 값들을 나누어 저장해야 할 수도 있습니다. 이때 구간에 아무리.. KOI 2021 2차 고등부 2번 풀이(그래프 균형 맞추기) https://www.acmicpc.net/problem/22344 22344번: 그래프 균형 맞추기 N개의 정점과 M개의 간선으로 구성된 무방향 단순 연결 그래프가 있다. 그래프의 정점들에는 1 이상 N 이하의 서로 다른 자연수 번호가 붙어 있고, 간선들에는 1 이상 M 이하의 서로 다른 자연수 www.acmicpc.net 개인적으로 1번 DP 생각해내는게 2번 풀이보다 어려웠다 2번 문제 해석과정에서 연립방정식을 생각해낼 수 있고, 이를 확장시키는 방식이다 먼저, 문제에서 주어진 예제를 해석해보았다. 왼쪽과 같은 그래프가 주어졌을 때 (1)번 정점의 값 C1을 기준으로 잡았을 때, 간선의 값을 반영하여 각 정점의 값을 표현해보면 C3 = 5 - C1 C5 = 3 - C3 = C1 - 2 C2 = -4.. KOI 2021 2차 고등부 1번 풀이(헬기 착륙장) https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 내 2차 대회 시간을 날려먹은 주범.. 수학 문제가 나오면 규칙을 찾을려고 하는 편인데 규칙이 잘 찾아지지 않다보니 시간을 많이 소비했었고 멘탈에도 안좋았던 문제이다 결론적으로는 DP 테이블을 만들어야지 풀이가 보이는 문제였다 먼저, 착륙장의 크기가 \(n\)일 때 필요한 페인트의 양은 \(i(i+1)/2\)이다 빨강 페인트를 \(x\)통 사용하였다면 파랑 페인트는 \(i(i+1)/2-x\)통이 필요할 것이.. 이전 1 2 3 다음
