hades

🥅 문제https://www.acmicpc.net/problem/17626 🔍 설계  모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있으므로, 그 자연수를 이루는 제곱수들의 수는 다이나믹 프로그래밍을 이용하여 구할 수 있다. 예를 들어, 61 = 5^2 + 6^2이므로 5^2의 최소 제곱수 개수인 1과 6^2의 최소 제곱수 개수인 1을 더해 제곱수 2개를 이용하여 구할 수 있다.  👊 풀이#include #include #include #include using namespace std;int n;vector dp(50001, 1e9 + 7);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; ..

🥅 문제https://www.acmicpc.net/problem/14500 🔍 설계처음에는 시작 좌표를 잡고, 그 좌표에서 시작하는 테트로미노 케이스를 모두 만들어서 값을 도출하려 했으나, 대칭과 회전까지 고려했을 때, 케이스가 너무 많아진다. 테트로미노의 특징은 인접한 칸으로 이루어져 있다는 것이다. 따라서, DFS를 이용하여 4개의 칸으로 이루어진 테트로미노를 만들 수 있다. (poli) 하지만, ㅗ 모양의 테트로미노는 인접한 칸으로 확장해나가는 DFS로 구할 수 없으므로, 따로 만들어야 한다. ㅗ 모양을 만드는 가장 쉬운 방법은 十 모양의 테트로미노를 만들고, 상하좌우에서 하나씩 빼면 된다. 十 모양을 구성하는데, 칸이 존재할 수 있는 범위를 벗어나는 경우에는 제외되었다고 생각하면 되고, 제외된..

🥅 문제https://www.acmicpc.net/problem/11726 🔍 설계직접 그려서 파악해보면, 파란색 화살표는 2*1 타일을 추가하여 만들어지고, 빨간색 화살표는 1*2 타일을 두 개 붙인 것을 추가하여 만들어진다. 즉, dp[i] = dp[i-1] + dp[i-2]라는 것을 알 수 있다. 👊 풀이#include #include #include #include using namespace std;int n;vector dp(1001);int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; dp[1] = 1; dp[2] = 2; for (int i = 3; i

🥅 문제https://www.acmicpc.net/problem/11724 🔍 설계서로소 집합을 사용하여 연결된 것들끼리 그룹을 형성하게 한다.  그룹의 수는 맨 꼭대기에 있는 조상의 수이다. 문제 입력 순서에 따라 parent[x]가 맨 꼭대기 조상이 아닐 수 있으므로, find_parent(x)로 맨 꼭대기 조상을 집합에 삽입한다. BFS로 방문처리를 하여 영역의 개수를 구하여 해결할 수도 있다. 👊 풀이1#include #include #include #include using namespace std;int n, m, u, v;vector parent(1001);set result;int find_parent(int x) { if (parent[x] != x) { return find_pa..

🥅 문제https://www.acmicpc.net/problem/11659 🔍 설계i번째부터 j번째까지의 합은 j번째까지의 누적 합에서 i-1번째까지의 누적 합을 빼면 된다. 주의할 것은 배열은 0부터 시작하지만, 입력으로 들어오는 것은 몇 번째에 대한 정보이므로 1부터 시작한다. 👊 풀이package hades.ps;import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n, m; n = sc.nextInt(); m = sc.nextInt(); int[] arr..

🥅 문제https://www.acmicpc.net/problem/11403 🔍 설계모든 i, j 쌍에 대하여 i에서 j로 이동할 수 있는지 묻고 있으므로, i에서 j까지 가는데 거리가 0보다 크기만 하면 된다. 모든 쌍에 대한 최단 거리를 구하는 플로이드 워셜 알고리즘을 이용하여 i와 j가 연결되어 있는지 확인할 때, 중간지점인 k를 설정하고, i와 k, k와 j가 연결되어 있으면 i와 j가 연결되어 있는 것으로 갱신한다.  👊 풀이#include #include #include using namespace std;int n, temp;vector> adj_matrix(100, vector(100));int main(void){ ios_base::sync_with_stdio(false); cin...

🥅 문제https://www.acmicpc.net/problem/11399 🔍 설계인출하는데 시간을 많이 쓰는 사람이 앞에 오면, 뒤에 사람들이 기다려야 하는 시간이 그만큼 늘어나므로, 인출 시간을 기준으로 오름차순으로 정렬한다. 어떤 사람이 인출하는데까지 걸리는 시간은 앞 사람들이 인출하는데 걸리는 시간 + 본인이 인출하는데 걸리는 시간이다. 👊 풀이#include #include #include using namespace std;int n;vector p;int main(void){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; p = vector(n); for (int i = 0; i > p[i]; } sort(p.begin(..

🥅 문제https://www.acmicpc.net/problem/11286 🔍 설계우선순위 큐를 사용하여 첫 번째 조건으로 절댓값을 비교하고, 두 번째 조건으로 절댓값이 같다면 실제 값을 비교하여 작은 것이 우선순위가 높도록 한다. 👊 풀이#include #include #include using namespace std;int n, x;struct compare { bool operator()(int a, int b) { if (abs(a) > abs(b)) { return true; } else if (abs(a) == abs(b)) { return a > b; } else { return false; } }};priority_queue, compare> pq;int mai..

🥅 문제https://www.acmicpc.net/problem/10026 🔍 설계상하좌우로 인접한 영역 중 같은 색을 가진다면 한 구역으로 인식한다는 것에서 BFS임을 알아차릴 수 있다. 적록색약인 사람과 적록색약이 아닌 사람의 경우를 나누어서 BFS를 수행한다. 적록색약이 아니라면, BFS가 시작되는 지점의 색깔과 같아야 한 구역에 포함되고, 적록색약이라면 시작되는 지점의 색깔이 빨간색 또는 초록색이면, 이웃한 지점의 색깔도 빨간색 또는 초록색이면 한 구역에 포함되고, 파란색의면 이웃한 지점의 색깔도 파란색이어야 한다. 👊 풀이#include #include #include using namespace std;int n;vector> painting1(100, vector(100));vector..

🥅 문제https://www.acmicpc.net/problem/9095 🔍 설계1 = 12 = 1 + 1 = 23 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 34 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 3 + 1 = 1 + 1 + 2 = 2 + 2 = 1 + 3으로 dp[i] = dp[i-1]+dp[i-2]+dp[i-3]이라는 것을 알 수 있다. dp[0]을 0으로 초기화하면, 1부터 반복문을 시작할 수 있다. 단, 범위를 주의해야 한다. 👊 풀이#include #include using namespace std;int t, n;vector dp(11);int main(void){ dp[0] = 1; for (int i = 1; i = 0) { ..