https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 구슬 N개를 그룹 M개로 나눈다. 각 그룹은 무조건 구슬이 1개이상이다. 모든 경우의 그룹을 나눴을때, 그룹의 최대값이 나올 수 있는 경우의 수 중 최소일때를 찾는다. 접근 방법이 도저히 떠오르지 않았다. 각 경우의 수를 모두 구해야하는 완탐으로 접근해야 하나,,? N이 늘어날수록 어마무시하게 시간복잡도가 높아질게 뻔히 보이므로 알고리즘적으로 접근방법을 찾아야만 한다,,, 진짜 모르겠다 멍..

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다.라는 조건에서 첫 번째 생각은 총 N일동 안 자신이 사용할 금액 중 가장 큰 값 이상이어야 문제조건 자체가 성립된 다는 것이다. 당연한 말인 게 남은 금액을 통장에 집어넣기 때문에 만약 사용할 금액 중 가장 큰 값보다 작다면, K원 인출, K원 집어넣기 무한반복 ,,,,,,, 이렇게 첫 번째 조건은 만족한 것 같고, 두 번째로는 정확히 M..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 이 문제를 보자 마자 생각이 든 문제는 별 찍기 문제였다. 2024.03.10 - [Algorithm/DFS] - [BAEKJOON] 2448번 별 찍기 - 11 [BAEKJOON] 2448번 별 찍기 - 11 https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 이 문제의 핵심은 이 그림을 가지고 어떤 규칙이 있는지 유추하는 것이 핵심이다. 같은 모양이 반복적으로 나타나는 구조인 프랙탈(?) 구조인 것을 볼 수 있다. 여기서 나의 접근 방법은 Top-Down Approach를 통 DFS로 결정을 했다. 3x2^k (0> n; dfs(n / 3, 0, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < 2 * n - 1; j++) { if (map[i][j] == ..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 처음 문제를 보자마자 그래프가 나오길래 그래프 탐색 방법을 떠올렸다. 접근 방법은 차례대로 인덱싱하는 방향이길래 왼쪽부터 차례대로 인덱싱할수 있도록 DFS방식으로 접근해봤다. 또한 각 레벨에서의 너비를 구해야하는데, 탐색할때마다 인덱스를 1부터 시작해서 하나씩 증가시켜주며(어차피 왼쪽에서 부터 차례대로 인덱싱 할거니까), 각 레벨의 low, high 배열을 갱신시켜서 왼쪽 끝과 ..

https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 지문이 너무 길어서 읽는 시간이 많이 걸렸던 문제였다. 첫번째 접근방식은 모든조건을 if문을 두어 풀어서 시간초과가 났다,,, 소스코드 #include #include using namespace std; int n, kim, im, cnt; //홀수 일때 마지막 한명 부전승 //라운드 마다 참가자의 번호를 순서 유지하며, 다시 번호 매김 int main(){ cin >> n >> kim >> im; c..