hyunjin

문제 풀이좀 조건이 까다로웠다. ( +1) -1로 놓고 생각했다.순차적으로 해당 위치를 반대 괄호를 바꿨을 때 불가능한 경우를 생각해보면 (단, 한번의 오타만 냈다는 조건이 중요하다)양끝단 검사. 맨 앞은 ( , 맨 뒤는 ) 이어야한다.최종적으로 ( ) 개수가 같아야하므로 맨 끝에 합이 0 나와야한다. ( → )  : 해당 위치에서  ~ 맨 끝에 음수가 있는지 확인.  ) → (  : 해당 위치에서 앞 부분에 음수 있는지 확인.( ) ) ( ( )  이 케이스를 생각해보면 된다.  1차 코드#include #define MAX_N 100001using namespace std;string str;int arr[MAX_N];int sum[MAX_N];int len;bool possible(int idx, ..

문제최소공배수 구하는 방법 $N =10^15$ 크다. 완탐하면 시간 초과 발생.접근의 핵심은 두 수 a,b의 최소공배수 개념 접근법최소공배수를 찾을 필요는 없지만 최소 공배수 개념을 활용해서 묶음의 가성비를 구한다. A :  2 개 →    3원      X 10B : 10개 →  14원      X  2 A :  20개 →   30원B :  20개 →   28원  win 묶음의 가성비는 B가 더 좋다.A의 묶음 개수 x, B의 묶음 개수 y라 할때만약, 총 x*y(최소공배수) 개를 사야한다면 B를 x개 사는 것이 더 이득이다.B를 x개 사는 게 더 이득이다. ==> A를 y개 이상 살 필요가 없다. (y-1개 이하일 땐 아니란 의미) 그러니 B에 묶음 가성비 좋은 가게로 설정해두고A를 y개 미만일 때까..

최대공약수 공식(유클리드 호제법) 두 수 a, br : a % b = a mod bgcd(a,b) = gcd(b, a % b) = gcd(b, r)int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}int gcd(int a, int b) { int r; while (b) { r = a % b; a = b; b = r; } return a;}   최소공배수 공식 (최대공약수 활용)최소공배수 * 최대 공약수 = a * b최소공배수 = a*b / gcd(a,b)int gcd(int a, int b) { return b ? gcd(b, a % b) : a;}int gcd(int a, int b) { int r; while (b) { r = a % b; a =..

문제 문제 포인트는 제거 이후 움질일 클러스터를 찾는 부분 문제에서 공중에 떠 있는 미네랄 클러스터는 없으며, 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우도 없다. 라는 조건이 주어졌다. 하지만 잘생각해보면 아래와 같은 케이스가 있다. 3 3 xxx x.x ..x 1 3 .xx ..x x.x 움직이는 클러스더가 (2,1) 하나이긴 하지만 (1,1)이 제거된 이후에 움직일 가능성이 있는 것은 (2,1)과 (1,2) 클러스터 2개이다. 물론 (1,2) 클러스터가 움직이지 않아서 결론적으로 하나의 클러스터만 움직이지만 그것을 확인하는 과정에선 여러 클러스터가 움직일 가능성이 있다고 판단. 처음엔 이걸 생각못하고 제거되는 위치의 아래는 확인하지 않았다. #include #include #include..

문제 S - G - H - T 혹은 S - H - G - T 의 경로가 S - T로 가는 최단 경로인지 확인하면 된다. 그래서 S,G,H 각각의 정점을 시작으로 하는 최단 길이를 다익스트라로 구한다. #include #include #include #include #define INF 0x7f7f7f7f #define MAX_N 2001 using namespace std; int N; int S, G, H; int dist[MAX_N][MAX_N], mdist[MAX_N], mdist_g[MAX_N], mdist_h[MAX_N]; bool vis[MAX_N]; void dijkstra(int start, int *d) { memset(vis, 0, sizeof(vis)); d[start] = 0; fo..

BOJ 20922 겹치는 건 싫어 O(N) #include #define MAX_N 200000 #define MAX_A 100001 using namespace std; int N, K; int arr[MAX_N]; int cnt[MAX_A]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; for (int i = 0; i > arr[i]; int ans = 1; int left = 0, right = 0; while (right < N) { int num = arr[right]; if (cnt[num] < K) { cnt[num]++; } else { while (arr[left] !..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 최장 증가 수열 (LIS, Longest Increasing Subsequence) 다이나믹 프로그래밍을 이용한 방법 : O(N^2) - 최장 길이 구하는 방법 앞 순서의 모든 원소에서 끝나는 최장 증가 수열들의 길이 중 가장 긴 것을 골라 1을 더한 것이 곧 현재 수에서 끝나는 최장 증가 수열의 길이이다. 따라서 dp..

문제 1차 코드 #include #include #include #include #include #define MAX_H 30 #define MAX_N 10 using namespace std; int N, H; bool grid[MAX_H+1][MAX_N+1]; vector candi; int ans = 10; bool InRange(int x) { return 0 ans) return; if (Verify()) ans = min(ans, cnt); if (cnt > 3) return; for (int i = start; i < candi.size(); i++) { int y, x; tie(y, x) = candi[i]; //선 겹침 if (InRange(x - 1) && grid[y][x - 1]) ..