나 요리학원 출신임

문제가 참 완탐스럽게 생겼다 처음에는 그리디로 쭉 보는건가 싶었는데 하다보니.. 그냥 편하게 백트래킹으로 풀었따 모든경우의 수 중에서 가지치기를 하면서 보면 시간안에 빠르게 들어온다 먼저 총 15가지의 라운드가 있고 각 라운드는 3가지의 경우의 수가 가능하다 그래서 3^15의 경우의 수가 있다 이 중에서 우리는 4개의 입력으로 받은 조건들을 만족하는 경우를 찾아야 한다 그래서 입력조건을 벗어나는 경우는 적절하게 가지치기를 해줘야한다 나의 경우는 order라는 배열에 일단 15라운드의 prev VS next를 다 저장했다 ex) [A,B],[A,C],[A,D]...[E,F] 그 후 order배열에 0(prev 승),1(무),2(prev 패)를 넣어보면 된다 그러게 status라는 배열에 현재 라운드의 결과..

3개로 묶었을 때 그 중 가장 작은 옷값은 할인을 해준다 그럼 그리디로 생각해서 묶으면 된다 어차피 제일 큰건 할인 못받는다 3*k 번째로 큰 애들만 할인 받을 수 있다 편하게 pq에 값을 넣고 탐색해보자! 자바는 min heap 이므로 -를 붙여서 넣으면 최대힙으로 바꿀 수 있다 그리고 pq에서 하나씩 꺼내보며 만약 3*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 25 26 27 28 29 30 31 32 import java.util.PriorityQueue; import java.util.Scanner; public class Solution { public static void mai..

숫자 제한들이 아주 작아서 그냥 제한 생각안하고 돌려도 잘 풀리는 문제다! 일단 인구이동을 어떻게 시킬지 생각해보자 간단하게 DFS를 이용하면 된다 나와 인접한 마을중 인구수 차이가 L이상 R 이하라면 그곳의 인구를 더해주고 체크해주자 이렇게 내가 갈 수 있는 마을의 모든 인구를 더하고 순서를 order에 담아 기억해주자 그럼 dfs가 끝나고 인구의 총 합 / 탐색한 마을로 order를 통해 사이좋게 나눠가지면 된다 이걸 언제까지해야할까 그냥 이동 할 일이 없을때까지 해보자! 이동이 없을 조건은 나 자신만 탐색하고 끝나는 경우다 그걸 cnt의 수가 1이하라면 안하는걸로 했다! 쉽게 생각하고 생각없이 짜면 잘 풀린다..! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..

다이어트를 하기위해 최적의 햄버거를 찾는 최고의 문제다 실생활에서 우리가 마주칠수있는 현실적인 문제 굿 일단 이 문제는 DP를 이용해서 풀 수 있다 내가 L 칼로리 이하를 먹어야만한다 그럼 N개의 버거 중 1) 현재 버거를 먹을때 2) 현재 버거를 안먹을때 두개를 비교해주면 된다 이 때 현재 버거를 먹기위해선 칼로리(sum+b[pos])가 L 이하여야 한다! 그럼 그 값들 중 최대값을 찾아보자! 소스코드 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 import java.util.Scanner; public class Solution { public stati..

문제를 읽으면 그냥 다익스트라처럼 생겼다 그래프를 그리고 내가 최소시간을 들여 원하는 정점으로 가면 된다 근데 조건이 하나 붙는다 100을 초과는 거리를 간다면 그때는 연료를 충전해야 한다 이걸 매번 정점에서 하는줄알고 처음에 틀렸다 ㅎㅎ 결국 내가 갈수있는 거리도 하나의 가져가야할 데이터가 되므로 테이블을 d[정점의 수][갈 수 있는 거리]로 잡아보자 => d[1010][111]; 최대 정점은 1000개고 갈수있는 거리는 한번에 100이다 그리고 다익스트라를 돌리면서 pq에서 내가 남은거리도 들고다니면 된다 만약 남은거리보다 다음정점까지 거리가 같거나 짧으면 그냥 가면된다 하지만 남은거리가 더 짧으면 시간 5를 추가해 충전하고 주행가능거리를 100이라고 생각하자! 그리고 마지막으로 정점 n+1에서 남은..

문제를 푸는것보다 이해하는게 더 어려운 문제같다 문제를 풀려면 그냥 쓰여져있는대로 코딩하면 된다! 하라는대로!! a와 b가 i-1이하기 때문에 무조건 이전에 계산한 식을 통해 값을 구할 수 있다 그럼 for문을 통해 N-1개의 값들을 먼저 저장하고 그걸 이용해서 f(x)값을 구해보자! 소스코드 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 import java.util.Scanner; public class Solution { static class Node { int tx,ax,bx; Node(int _t..

옛날에 풀어본 문제여서 다시 풀어보려고 했는데 탈탈 털렸다 옛날에는 어떻게 풀었을까? 도움을 받았었나 ㅎㅎ 이 문제는 하이퍼링크는 연결되어있기 때문에 안에서는 비용이 안들고 하이퍼링크를 넘어갈 때는 비용이 든다는걸 그래프로 표현해야한다 어떻게 해야할까..! 그래프를 만들때 (N+M)개의 정점으로 만들어주면 된다! 1~N 까지는 정점이고 (N+1 + M)까지는 바로 하이퍼링크..! 내가 어떤 점 X 가 하이퍼링크 K에 속해있다면 그래프 X에서는 갈 수 있는 하이퍼링크 K에 연결시켜주고 1의 비용이 들고 반대로 하이퍼링크 K 에서는 갈 수 있는 점들 X를 연결하고 하이퍼링크 안에서 이동이므로 비용은 0이 된다! 그래서 그래프를 만들면 X -> K (비용 1) 하이퍼링크 밖에서 이동 (정점 X를 가진 하이퍼링..

오래 고민한 문제다..! 이런거 참 생각을 잘 못하는거같다 어떤 화분을 깨면 화분에 해당하는 숫자가 오른쪽에 임의에 화분에 있다면 그 화분도 깰수있다 계속 연속적으로 이어져간다 자 생각을 해보자..! 맨 처음 화분은 무조건 깨야만한다. 안그러면 아무도 깨주지 않으므로..! 그럼 맨 처음 화분에 포함되는 수를 앞으로 만난다면 그 화분도 무조건 깨져야한다 그럼 입력받으면서 처리할 수 있다..! 화분을 깨지는 수를 계속 저장해가며 하나라도 가지고 있으면 깨버리자! 소스는 참 짧다! 처음에는 set을 썼는데 그럼 시간이 너무 오래 걸린다 배열을 이용하자 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include using namespace std; #define ll long..

참 어려워 보이는 문제다 근데 생각해보면 쉬운 문제다 물론 long long 안써서 처음에 틀렸다 ㅎㅎ 먼저 우리가 알아야할 x들은 소수라는 점을 기억하자 그럼 c1,c3,c5,c6은 소수 2개의 곱이므로 유일한 수 2개가 있을 것이다. 결국 완탐하면 된다! 이 문제에서 x4랑 x8은 의미없다 쓰지 않는다 완전탐색을 할 때 어떤 수 2개를 곱해서 c가 되야하므로 i*ic1>>c2>>c3>>c4>>c5>>c6; vector x1,x2,x3,x4,x5,x6,x7,x8; solve(c1,x1,x2); solve(c3,x6,x7); solve(c5,x2,x3); solve(c6,x6,x5); for(int a=0;a

수학 공부 열심히 한다는 마음으로 항상 틀리며 공부하고있다 ㅎㅎ 이 문제를 풀 때 혼자 너무 어렵게 접근해서 처음에는 반도 못갔다 코포 끝나고 혼자 풀어보니까 f(a,b) = a&(-b) 로 정리된다는걸 깨달았다 근데 거기서 발전은 못해서 에디토리얼을 봤다 ㅎㅎ 어렵다..!! 결국 a1~an까지 정리하면 a1&(-a2)&(-a3)&(-a4)...&(-an)이 된다는 걸 알 수 있다 그럼 여기서 주목할 건 내가 어떤 2^k 승의 비트를 가지는 수가 1개라면 그걸 a1에 놨을 때 나머지 a2~an까지 -가 붙기 때문에 2^k 위치를 살려준다! 예를들어 2^5 비트가 1인 수가 딱 1개만 있고 그걸 a1에 둔다면 나머지 수들은 2^5가 0이지만 -가 붙어서 1로변하고 a1에 놓인 2^5가 계속 1일 수 있다 ..