나 요리학원 출신임

그리디로 풀 수 있는문제라고 해야할까?! 서로 겹치는 부분이 있다면 방에 갈 수 없다 문제를 풀기 위해서는 뒤부터 보자! 나는 pq를 사용했다 내가 더 뒤에있는 사람부터 보면서 구간을 [a,b]라고해보자 그럼 나의 뒤에있는 사람은 [a`,b`]라고 할 때 1) 갈 수 있는경우 a`b 이 때는 구간이 겹친다 따라서 a`를 저장해뒀다가 다시 pq에 넣어두자 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include using namespace std; int n, t; int main() { scanf(" %d", &t); for (int tc = 1..

수학 + 큐 문제다 시물레이션으로 풀 수 있는데 숫자 범위가 int다 최악의 경우에 21억이 8개들어오면 대충 7억번? 돌아야한다고 생각하는데 그냥 풀어도 시간안에 들어오나보다 최악의 테케가 없는건지 아니면 내가 잘못생각한거지..! 어쨌든 문제는 5바퀴를돌면 총 15씩 전체적으로 감소시킬 수 있다 그럼 우리가 감소시킬 수 있는만큼 15*k만큼 감소시키자 그리고 시물을 돌리면 편하게 답이 나온다 직접 큐를 사용하지는 않는다 그냥 q의 top이 있다고 생각하고 top을 옮기는게 더 편하다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.io.FileInputStream; imp..

문제를 잘 읽어보면 한가지 알고리즘이 떠오른다 LCA!!! 간만에 떠올라서 잠깐 다시 공부하고 오랜만에 만들어봤다! 먼저 이 문제는 1이 루트고 bfs로 나머지 정점들에 순서대로 계속 가기 때문에 정점 2개씩 잡으며 lca를 구해서 lca까지의 거리를 더해가면 답을 구할 수 있다 lca만 알면 쉽게 풀 수 있는 문제다! 근데 더 어려운건 swea에서 스택메모리가 1메가라그런지 dfs로 깊이를 매기니 런타임 에러가 났다;; 대체 어디가 틀린지 몰랐는데 이게 틀렸었다;; bfs로 바꿔서 깊이를 찾았다!! 함수였던건 다 메인으로 넣어버렸다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..

트라이 기본 문제다. 트라이 짜는법을 마지막으로 정적으로 배웠기 때문에 정적트라이를 이용했다! 문제를 푸는 방법은 간단하다 트라이를 만들고 cnt배열을 만들어서 지나가는 정점마다 cnt를 올려주면 된다 그럼 내가 어떤 지점에서 시작한다고 할 때 그 수만큼 cnt가 올라갈 것 이다 근데 문제는 초기화가..! 문제였다 정적으로 잡기 때문에 노드의 수를 미리 max로 두고 시작한다 여기서는 100000개의 쿼리 X 10자리수 X 알파벳 26개 다 근데 바보같이 초기화 하는 부분에서 max 크기만큼 모든배열을 계속 초기화했다 시간초과가 정확히 30번 났다 혹시 오타가 났나 계속 다시 짰는데 문제는 초기화였다 생각해보면 초기화는 내가 사용한 정점까지만 해주면 된다 trie_cnt에 저장해놨기 때문에 딱 이만큼만 ..

DP 문제다! 아직도 DP에서 실수가 많다... 완탐으로는 불가능하니까 중복되는 정보를 줄여보자 테이블은 d[현재위치][남은 점프 수]로 잡는다 처음에 틀렸던 이유는 이전에 뛰어온 곳을 저장하려고 했기 때문이였다 현재위치만 가지고 다음에 뛰어갈 곳을 구해서 정보를 업데이트하면 되는데 테이블은 이전에 정보를 가지지도 않으면서 나는 이전에 어디서 왔는지 정보를 들고다녔다 처음 테케만 나오고 바로 틀렸따~! 틀린 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include #include using namespace std; cons..

조금은 수학적인 문제다 3N+3 = 3(N+1)로 바꿀 수 있다 그럼 N이 홀,짝으로 나눠서 경우를 생각해보면 된다 3은 홀수 이므로 짝수가 되어 2로 나누어도 3은 계속 남는다 이 원리를 생각해보자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include #include using namespace std; #define ll long long int main() { //freopen("input.txt", "r", stdin); int tcase; scanf(" %d", &tcase); int c = 1; while (tcase--) { ll n; scanf(" %lld", &n); while (n % 2 == 0) n /= 2; string ans = (n == 1..

투 포인터를 이용하면 쉽게 풀 수 있다 간격을 보면서 끝까지 답을 갱신해 가면 나온다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namespace std; int n, k; int arr[1010]; int main() { //freopen("input.txt", "r", stdin); int tcase; scanf(" %d", &tcase); int c = 1; while (tcase--) { memset(arr, 0, sizeof(arr)); scanf(" %d %d", &n, &k); for (int i = 0; i

이분탐색을 통해 풀 수 있는 문제다 X일을 mid로 설정해보자 그 후 정렬을 하고 mid값으로 설정했을 때 숙제를 할 수 있는지 하나하나 확인해보자! 시간이 좀 걸린다..! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include #include #include using namespace std; #define ll long long const int MAXN = 1e6 + 5; int N; pair arr[MAXN]; bool solve(ll mid) { ll now = mid-1; for (int i = 0; i ..

이 문제는 써있는게 요란해서 그렇지 사실 dp로 풀면 바로 풀 수 있다! 우리가 생각해야할 조건은 4가지다 x,y,숫자,방향! dp테이블을 d[x][y][num][dir]로 잡아보자!! 다 잡았으면 이제 dp테이블의 값을 생각해보자 d[x][y][num][dir]은 바로 x,y위치에서 num의 숫자를 가지고 dir 방향으로 갈 때 처음 방문하는곳이라면 -1 , 이미 방문했으면 0, 멈출 수 있다면 1이다! 이제 각 문자에 맞게 조건을 return 해주면 된다! 0,0 에서 시작해서 1이 될 수 있는지 봐야하므로 비트연산 or 을통해 계속 return 해주자! 나는 소스 중복되는 부분이 많게 풀었다..! 4방향 가는거 함수 하나로 만들어서 해도되는데..! 다들 짧게 푸시길! 소스코드 1 2 3 4 5 6 ..

이 문제는 투 포인터의 개념으로 풀 수 있다! 디스크가 쌓여져있는 모습을 생각하며 전처리를 해줘야한다 각 디스크 자리에 들어갈 수 있는 최대의 수를 미리 구해보자! 그리고 아래서부터 들어가 쌓이므로 거꾸로 최대의수 배열을 보며 디스크를 넣어보면 된다 while문을 통해 내가 현재 넣을 수 있는 가장 아래칸을 찾고 위치를 계속 갱신해 나간다 그리고 마지막으로 우린 뒤집어서 봤으므로 다시 위치를 뒤집는다! 디스크를 넣을 수 있는 N개의 칸을 모두 다 지나쳐 버리면 답은 0이 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #inclu..