hades

🥅 문제https://www.acmicpc.net/problem/16928 🔍 설계주사위를 던져서 이동하는데, 이동한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다. 올라간다는 것은 현재 위치한 칸보다 번호가 큰 칸으로 이동한다는 것이고, 내려간다는 것은 현재 위치한 칸보다 번호가 작은 칸으로 이동한다는 것이다. 주의헤야할 것은 사다리나 뱀을 만나면 무조건 이용해야 하고, 한 칸에 사다리가 있거나, 뱀이 있거나, 비어있다는 것이다. 출발지인 1에서 목적지인 100까지 이동하기 위해, '사다리는 높은 번호의 칸으로 이동시켜 때문에 사다리만 사용하면 좋은 것 아닌가? '라는 생각을 할 수 있지만, 무조건 사다리만 이용해야만 좋은 결과가 나오리라는 보장..

🥅 문제https://www.acmicpc.net/problem/1766 🔍 설계먼저 푸는 것이 좋은 문제를 먼저 푼다는 것에서 두 문제 간의 순서가 정해져 있고, 위상 정렬임을 쉽게 파악할 수 있었다. 추가로 우선순위가 같은 경우, 쉬운 문제를 먼저 풀기 때문에 진입 차수가 0이 되었을 때, 바로 출력하지 말고, greater 우선순위 큐를 이용하여 진입 차수가 0인 문제 번호를 담아 빼낼 때마다 출력하도록 한다. 👊 풀이#include #include #include #include #include using namespace std;int n, m, a, b;priority_queue, greater> pq;vector degree(100001);vector> adj_list(100001);v..

🥅 문제https://www.acmicpc.net/problem/1138 🔍 설계큰 것을 먼저 배치하면, 선택의 폭이 많기 때문에 좋지 않다. 작은 것, 즉 앞에 있는 것부터 배치한다. 작은 것부터 배치하기 때문에 반복문으로 순회하면서 큰 것이 있는 상황은 고려하지 않아도 된다. 순회하는 과정에서 채워지지 않아서 0이라면, 자신보다 큰 사람의 수에서 1을 뺀다. 계속해서 빼다가 -1이 되면 배치한다. 👊 풀이 #include #include #include using namespace std;int n, smaller;vector v(10);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i ..

🥅 문제https://www.acmicpc.net/problem/2252 🔍 설계두 노드 간의 순서가 정해져 있고, 답이 여러가지인 경우에는 아무거나 출력하라는 것에서 전형적인 위상 정렬임은 쉽게 파악할 수 있었다. 다만, 다시 기억시키기 위해 알고리즘 파트에 정리하였다. 👊 풀이#include #include #include #include #include using namespace std;int n, m, a, b;vector degree(32001);vector> graph(32001);void topology_sort() { queue q; for (int i = 1; i > n >> m; for (int i = 0; i > a >> b; degree[b] += 1; graph[a].p..

🥅 문제https://www.acmicpc.net/problem/2143 🔍 설계부배열의 형태를 보면, 누적 합을 이용해야 한다는 것은 쉽게 파악할 수 있다.  처음에는 A와 B의 부배열을 구해서 서로 다른 맵에 저장한 후, 한 쪽에서 반복자를 사용해 반복하면서, (T - 한 쪽에 있는 부배열의 합)이 다른 쪽에 있으면, (한 쪽에 있는 부배열의 합의 개수) * (다른 쪽에 있는 부배열의 합의 개수)로 구하려고 했으나 메모리 초과가 발생하였다. 맵 하나가 최대 1000000개 * 2 * 4Bytes 이므로 64MB를 초과하기 때문이었다. 그래서, 맵을 하나만 만들고, 다른 쪽에서 부배열의 합을 만들면서 바로 찾는 방식을 사용하였다. 부배열의 합을 만들기 위해 이중 반복문을 사용하기 때문에 100000..

🥅 문제https://www.acmicpc.net/problem/1202 🔍 설계가방에는 가방이 담을 수 있는 무게 이하의 보석만 담을 수 있다. 보석을 어떻게 담을지가 문제다. 보석과 가방의 무게를 오름차순으로 정렬하고, 가방마다 담을 수 있는 보석 중 최대 가치를 결과에 더하면 된다.  최대 가치는 우선순위 큐를 이용하여 구한다. 탐색하는 보석에 대하여 인덱스를 공유하면, O(N+K)로 해결할 수 있고, 우선순위 큐를 공유함으로써 그 가방 최대 무게 이하의 보석을 고려할 수 있다. 👊 풀이#include #include #include #include using namespace std;int n, k, m, v, c, p = 0;long long result = 0;vector> jewel;v..

보호되어 있는 글입니다.

🥅 문제https://www.acmicpc.net/problem/1562 🔍 설계0~9까지의 모든 수를 포함하는 계단 수가 몇 개인지 구해야 한다. 길이가 n인 것이 n+1인 계단 수를 이루는 데 사용될 수 있으므로, 다이나믹 프로그래밍을 이용한다. 사용한 숫자를 기록하기 위해 비트마스킹을 이용한다. 9만 사용되었다면, 이진수로 1000000000인 512에 저장하는 방식이다. dp[사용한 숫자][길이][마지막 숫자]로 구상한다. 다이나믹 프로그래밍이므로, 초깃값을 설정해야 하는데, 길이가 1이라면, 계단 수의 개수는 그 수만 해당되므로 1로 설정한다. 길이가 2 이상일 때, 0으로 끝난다면 마지막 수가 1만 되고, 9로 끝난다면 마지막 수가 8만 되고, 그 사이라면 마지막 수는 ± 1이 된다. 새로..

🥅 문제https://www.acmicpc.net/problem/1509 🔍 설계부분 문자열들 중에서 어디서부터 어디까지 팰린드롬인지 먼저 구해야 한다. 팰린드롬을 구하는 방법은 다음과 같다. 문자 개수가 하나인 경우, 팰린드롬이다.문자 개수가 2개인 경우, 두 문자가 같으면 팰린드롬이다.문자 개수가 3개 이상인 경우, 맨 앞과 맨 뒤가 같고, 가운데가 팰린드롬이면, 팰린드롬이다. 이제 팰린드롬을 구했으니, 최소로 분할해야 한다. 최소 분할 수는 반복문으로 어떤 인덱스까지의 최소 분할 개수를 저장하면서, 구할 수 있다. 주의해야할 점은 팰린드롬이 기본적으로 성립해야 한다는 것이다. 기존에 저장된 값과 0부터 end 사이의 인덱스를 start라고 할 때, start부터 end까지 팰린드롬이 성립한다면,..

🥅 문제https://www.acmicpc.net/problem/6198 🔍 설계처음에는 벡터에 높이들을 모두 저장하고, 이중 반복문을 수행하려고 했으나, 시간 복잡도 O(N^2)에 의해 시간 초과가 발생할 것이다. 건물 관리인들은 오른쪽만 보기 때문에, 반복문으로 건물 하나의 높이를 고려하면서, 스택에 그 건물을 볼 수 있는 다른 건물들을 저장한다.  만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 낮거나 같다면, 새로운 건물과 이후에 나오는 건물들을 볼 수 없으므로 이제 결과에 영향을 주지 않기 때문에 지운다. 만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 높다면, 그 건물에서 새로운 건물을 볼 수 있으므로 스택에 있는 건물의 개수를 추가한다. 👊 풀이#include #i..