hyunjin

문제   #include#include #include using namespace std;int N;char tree[102];void inorder(int id) { if (!tree[id] || id > N) return; inorder(id * 2); cout > T; for (int test_case = 1; test_case > N; for (int i = 1; i > id >> c; tree[id] = c; //방법1 string str; getline(cin, str); // 방법2 // int tmp; //while (getc(stdin) == ' ') // cin >> tmp; } cout

보호되어 있는 글입니다.

문제 링크코드 문제주어진 그래프에서 t 단계 별로 인접한 노드와 연결 엣지 지워나감.최초로 사이클 생성되지 않는 t 구하기N,M  풀이 전략사이클이 사라지는 것을 찾긴 어렵다.  → 사이클 생성 여부 확인으로 바꾸면 쉽다.주어진 순서대로 간선을 지우고 사이클 생성 여부를 확인 , 지울때마다 사이클을 판단 → TLE그렇다면 역순으로 판단하자.  마지막에 사라졌던 간선들부터 시작하여 처음 사라진 간선들 순서로 그래프가 복원하자.간선이 지워지는 역순으로 그래프를 생성해나가 보면, 어느 순간 사이클 발생 →  (전체 T - 사이클 생성 되는 t) 가 답 요약간선이 언제 지워지는지는 알겠음 : BFS를 적절히 응용지워지는 역순으로 간선을 연결해나가가다가 사이클이 생기는 시점 판단인풋으로 주어지는 K개 시작 노드를..

문제   1. Top Down, 재귀N에 도달 가능 여부만 판단한다.#include #include #include #define MAX_N 5001using namespace std;int N, K;int e[MAX_N], dp[MAX_N];// top - down// 도달 가능 여부만 확인하면 된다// 갈 수 있으면 바로 끝 // 2중 for 사용 가능int canGo(int target) { int& ret = dp[target]; if (ret != -1) return ret; ret = 0; //0으로 설정, 일단 못간다 세팅 // i -> target으로 이동 for (int i = 0; i > N >> K; for (int i = 0; i > e[i]; ..

문제 풀이좀 조건이 까다로웠다. ( +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..