나 요리학원 출신임

구현하면 되는 쉬운 문제다 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 += ..

총 N개의 입력이 들어오고 매번 입력마다 중간값을 출력하는 문제다 N이 최대 10만이기 때문에 N^2은 불가능하다! 자료구조 힙을 사용하면 된다 중간만 보기때문에 중간을 기준으로 양쪽을 힙으로 잘랐다고 생각하자 계속 첫번째 힙에 숫자를 넣어주고 만약 짝수번째 순서면 두번째 힙으로 넘겨주자 그리고 처리할게 하나 있는데 첫번째힙의 탑과 두번째 힙의 탑을 비교해서 첫번째 힙에 작은수가 들어갈 수 있게 해야한다 그럼 첫번째 힙의 top이 계속 답이된다! 참고로 첫번째는 max힙, 두번째는 min힙이다 소스코드 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 #include #include #include using namespace st..

수학문제다 가성비 좋아하는 사람을 맞출 수 있는 문제다 굿 우선 최소라는 말에 집중을 하자 처음보면 세번째 예제가 왜 저가격이 나오는지 이해가 안될수있다 하지만 생각해보면 양념 후라이드 따로사는거보다 저기서는 반반치킨을 200000 사는게 이득이다 결국 X,Y개중에 적은개수만큼은 (양념,후라이드)개를 살지 (반반*2)개를 살지 정하고 남은 숫자들 중에서도 양념따로 후라이드 따로사는것과 반반*2로사는걸 비교해보면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include #include using namespace std; #define ll long long ll A,B,C,X,Y; int main(){ scanf(" %lld %lld %lld %lld %lld",&A,&..