나 요리학원 출신임

완탐으로 풀 수 있어서 dfs를 이용해 풀었다 팀을 나눈 후 그래프로 표현하고 dfs를 이용해 내가 우리팀에 갈 수 있는지 체크를 하면 된다 여기서 만약 애초에 그래프가 2개 이상의 연결요소로 구성되어있다면 애초에 2개의 팀으로 나눌 수 없어서 -1 을 출력하고 종료하자! 그럼 그래프를 그린 후를 생각해보자 dfs를 이용해서 origin -> next 로 갈 수 있는지 계속 확인해보며 된다 그 후 만약 같은 팀인데 연결 되어있지않다면 false 아니면 true를 리턴해주고 만약 모든 조건을 만족한다면 팀의 합의 최소를 구해보자 소스코드 (C++) 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..

한번 풀어보려고했는데 한시간이나 걸렸따... 문제를 쉽게 해주기 위해 괄호는 하나의 연산자만 포함한다는걸 모르고 풀다가 나중에 보니 답이 다르게나온다~! 그리고 처음에 한자리수만 줘서 더 쉬운것같다 나처럼 복잡하게 푼 사람은 많이 없을듯..! 그럼 문제를 풀어보자! 우선 비트를 이용해서 짝수 인덱스인 숫자만 봐준다 괄호가 짝이 맞아야 하기 때문에 짝수개 있을 때만 넘겨준다! 110101이면 1~2 ,4~6이 괄호다! 괄호를 체크하고 solve 함수로 넘겨준다 그럼 solve는 괄호가 있는곳은 먼저 cal함수로 계산해주고 마지막에 괄호가 없을 때를 계산해 답으로 넘겨준다 cal에서는 순서대로 앞에서 계산하기 때문에 덱으로 그냥 계산했다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

구현하면 되는 쉬운 문제다 A와 B가 자리수가 같기 때문에 최대 보는게 100만개고 최대 자리수가 6자리다 그냥 구현하는데 중복을 제거하기 위해 set을 사용했다! 중복을 그대로 세면 틀린다! 소스코드 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 #include #include #include #include using namespace std; int x, y; string Y; int solve(string s) { int ret = 0; int n = stoi(s); int len = s.length(); set st; for (int i = 1; i

A와 B의 규칙을 잘 생각해보자 우리는 S->T 가 아닌 뒤집어서 T->S로 문제를 풀어본다! 1) 맨 뒤에 A를 붙인다 2) 맨 뒤에 B를 붙이고 뒤집기 => 뒤집고 앞에 B 붙이기 그럼 문제를 풀기 위해 나올 수 있는 상황 4가지를 생각해보자 1. A ~ A => 1번경우 가능 2. A ~ B => 불가능 3. B ~ A => 1,2 번 가능 4. B ~ B => 2번가능 4가지를 그대로 코딩해주면 시간안에 충분히 나온다! 소스코드 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 #include #include #include using namespace std; string s, t; bool solve(strin..

생각하며 풀어야하는 문제다! 이런 쉽게쉽게 생각하고 최적을 찾는 문제 잘푸는 사람들이 있던데.. 나는 아니다 ㅎㅎ 처음에 거꾸로 정렬시키고 투포인터로 뒤에서부터 보면 무조건 된다고 생각했다 근데 대충 테케를 만들어보다가 2 4 5 6 7 8 8 9 50 100 이걸 넣었다가 내 코드에서는 7이 나오는걸 발견했다 답은 6..! 생각해보면 최대답은 2/N이다 박스에 한개만 넣을수 있기 때문에! 그럼 우리는 반으로 잘라서 0~2/N, N/2+1~N 까지 l,r로 나눠서 넣어보면 된다! 풀고나면 참 쉬워보이는 문제.. 근데 한번에 떠올리기가 참 쉽지않다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include #include using namespace s..

쉬운 문제라고 생각해서 풀었는데 틀렸다 그리고 계속 생각도 거꾸로해서 방법을 못떠올렸다 문제는 자기와 색이 다르고 나보다 작은공을 먹을 수 있다는 내용이다 문제를 보고 거꾸로 생각했다 미리 합을 다 구해두고 크기를 기준으로 거꾸로 정렬해서 현재 나의 크기의 합들과 나의 색들의 합들을 빼야지했는데 두개의 교집합 부분을 다시 더해주기가 힘들어서 못했다 찾아보니 완전 거꾸로 생각하고있었다 반대로가면 쉽다 내가 여태까지 본 크기의 집합들과 색의 집합들을 가져가면 오히려 쉽다 크기를 기준으로 오름차순 정렬을하면 나는 다음 볼에 영향을 주는 볼이다 결국 생각해보면 현재 볼 = (여태까지의 합) - (같은 수의 크기 합) - ( 같은 크기의 크기 합) + 내크기 이렇게 하면 된다 집합이라고 생각하니 그림이 그려진다 ..

처음 스터디하다가 배웠을 때 신기했던 문제다 이 문제는 다익스트라르 풀 수 있다! 다익스트라로 어떻게 풀어야할까 쓰레기는 최대한 안지나고 쓰레기 옆길도 안지나고싶다 그럼 가중치를 쓰레기에는 5000, 옆길은 1을 줘보자! 5000을 주는 이유는 나올 수 없는 값을 주기 위해서다 왜냐면 나중에 5000으로 나눌거라서 ㅎㅎ 문제를 푸는 방법을 생각해보자! 1. 먼저 가중치를 쓰레기는 5000, 쓰레기 4방향으로는 1을 주자 2. 그리고 다익스트라를 통해 목적지까지 간다면 최소비용으로 가는 길을 찾을 것이다 3. 그럼 우선순위는 빈칸-> 쓰레기 옆길 -> 쓰레기가 된다 4. 마지막으로 쓰레기를 지나쳤다면 5000a , 옆길을 지나치면 b라는 가중치가 있을것이다 => 5000a+b가 될테니 /5000을 한다면 ..

A형에 MST가 나왔다던데 이 문제다 완탐으로 풀 수 있는데 괜히 MST한번 써봤따 그리고 틀렸따~~! -1을 출력하는 경우를 잘 생각해야한다 mst에서 정점이 n개일때 간선은 n-1개다 이 성질을 생각해서 -1을 정해주면 예외가 사라진다! MST 자체를 만드는건 유니온 파인드를 이용해 할 수 있다 거리 순으로 정렬하고 만약 A,B 정점이 부모가 다르다면 merge를 시켜준다 그렇게 모든 정점을 연결하면 MST가 완성된다! 그럼 문제를 푸는 순서를 생각해보자 1. 먼저 각 섬마다 넘버링을 해서 섬을 구별시킨다 =>dfs 2. 그리고 각 섬에서 다른 섬으로 거리를 구해보자 이 때 직선으로만 가능하니까 그냥 완탐 돌리자 3. 모든 섬에 대해 그래프를 만들어준다 4. MST를 만들자! 소스코드 1 2 3 4 ..

옛날에 생각 못하고 넘어갔는데 다시보니 너무 쉽다..! 처음을 A, 다음을 B라고 생각하고 몇번 써보면 피보나치가 완성이 된다 그리고 알 수 있는 규칙은 B = fib[A+1]이라는 사실이다 이걸 이용해서 식을 풀어보자 수학으로 풀 수 있다! aA + bB = K 인것을 이용해보자 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int A[33]; int B[33]; int D, K; int main() { A[1] = 1; B[2] = 1; for (int i = 3; i

그리디 문제다 큰 색종이부터 붙여보면 된다 근데 헷갈린다.. 함수화를 잘하면 코드가 짧아지는거같은데.. 나는 무식하게 짰다 진짜 다 붙여보자! 소스코드 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include using namespace std; int arr[7],ans; int solve(int size) { int ret = 0; if (size == 6) ret += ..