공부혜옹

제일 먼저 문제 푸는방법을 효율적이지 않은 방법으로 막 생각해보았다 1. 숫자를 전부 준비한다 2. 재귀를 이용해 10의 n제곱으로 나누면서 각 자리수의 크기를 확인한다 블로그에 쓰기도 부끄러운 해결방법이었지만 일단 이러한 과정을 통해 당연히 시간초과가 날것이니 다른 방법을 찾아야지라는 생각을 하게 되었다. 사실 DP 문제이기 때문에 점화식을 찾으면 되는데 점화식 찾는것에 자신이 없다보니 브루트포스로 밀 수 있는지 한번 생각해봤다. 이제 어쩔 수 없이 점화식을 찾아보자 우선 DP배열의 메모이제이션을 어떻게 배당할 것인가를 결정했다 그다음 점화식을 찾기위해 예시로 dp[2][4]를 분석해보았다 dp[2][4]란 두자릿수의 숫자중 4로 끝나는 오름수의 갯수를 뜻한다. 두자릿수중 끝자리가 4이니 결국 우리가 ..

#include #define endl "\n" using namespace std; int N, K, Answer; int Add_Water(int x) { int Cnt = 0; while (x > 0) { if (x % 2 == 1) { Cnt++; } x = x / 2; } return Cnt; } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> K; if (N

부분합 0.5 초 (하단 참고) 128 MB 29040 7511 5344 25.557% 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 이중포문을 쓰려다가 투포인터 기본문제라고 해서 투포인터를 사용해 풀어보았다. 알아보니 ..

세그먼트 트리를 이용해 구간 합을 구하는 문제였다. 트리의 각 노드에 모든 하위 노드의 합을 저장하여 구간합을 구하는 방식으로 문제를 풀이했다. #include #include #include #include using namespace std; typedef long long ll; ll init(vector &a, vector &tree, int start, int end, int node) { if (start == end) return tree[node] = a[start]; int mid = (start + end) / 2; return tree[node] = init(a, tree, start, mid, node * 2) + init(a, tree, mid + 1, end, node * 2 +..

기차가 어둠을 헤치고 은하수를 시간 제한메모리 제한제출정답맞은 사람정답 비율 1 초 512 MB 1898 527 405 28.867% 문제 N개의 기차가 어둠을 헤치고 은하수를 건너려고 한다. 기차는 20개의 일렬로 된 좌석이 있고, 한 개의 좌석에는 한 명의 사람이 탈 수 있다. 기차의 번호를 1번부터 N번으로 매길 때, 어떠한 기차에 대하여 M개의 명령이 주어진다. 명령의 종류는 4가지로 다음과 같다. 1 i x : i번째 기차에(1 ≤ i ≤ N) x번째 좌석에(1 ≤ x ≤ 20) 사람을 태워라. 이미 사람이 타있다면 , 아무런 행동을 하지 않는다. 2 i x : i번째 기차에 x번째 좌석에 앉은 사람은 하차한다. 만약 아무도 그자리에 앉아있지 않았다면, 아무런 행동을 하지 않는다. 3 i : i..

LCA 시간 제한메모리 제한제출정답맞은 사람정답 비율 3 초 256 MB 10393 4685 2711 43.578% 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다. 트리의 두 노드..

트리 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 128 MB 21823 5301 4166 25.887% 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 ..

배열에서 이동 문제 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 거쳐서 이동하게 된다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(2≤n≤100)이 주어진다. 다음 n개의 줄에는 배열이 주어진다. 배열의 각 수는 0보다 크거나 같고, 200보다 작거나 같은 정수이다. 출력 첫째 줄에 (최대 - 최소)가 가장 작아질 때의 그 값을 출력한다. 처음에는 단순히 bfs로 완전탐색을 하면서 최소와 최대값을 찾아 차를 구해주었는데 이렇게 하니까 당연히 시간초과가 ..