Written

완전탐색 혹은 백트래킹 문제를 많이 풀어봤다면 쉬운 문제였다고 생각합니다. 현재 피로도가 입장할 던전의 최소 피로도보다 크거나 같다면 방문처리 및 피로도 감소 처리를 하면서 다시 Search를 호출하는 형태로 진행했습니다. 더이상 들어갈 던전이 없으면 지금까지 들어온 던전의 갯수를 ans에 넣어주고 마지막에 ans를 sort를 이용해 정렬해주면 됩니다. 입력 역시 시간초과에 걸릴만한 크기가 아니기 때문에 비교적 쉽게 정답처리를 받았습니다. 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 #include #include #include using namesp..

처음 제출을 하고 테스트케이스 1번은 실패 그리고 11번과 30번대에서 시간초과를 하나씩 받았습니다. 시간초과기 때문에 while문을 유심히 살펴봤습니다. 결국 종료 조건을 통과하지 않는 경우의 수가 존재하는건데, 그 케이스를 처리하지 못하기 때문이라 생각하고 반례를 생각해봤습니다. 그리고 처음 든 생각은 [2,2,2,2] [2,2,2]과 같은 경우에는, 코드대로 큰 큐에서 작은큐로 이동할 것이기 때문에 2 하나가 무한으로 왔다갔다 하면서 cnt만 올라가니 cnt를 제한해야 한다고 생각했습니다. 그래서 cnt의 제한을 어떻게 두어야 하나 고민하다가, 큐1과 큐2의 사이즈를 더한거보다 커지면 두 큐의 합을 같게 만들지 못하는걸로 결론내리고 제출했습니다. 그리고 1번은 그대로 실패. 11번과 30번의 시간초..

discount의 구간을 앞에서 부터 10개씩 잘라가면서 각 구간에서 내가 사려고 하는 물품들을 전부 살수 있으면 카운트를 하나씩 늘려주는게 가장 먼저 떠오른 풀이방법이었습니다. 완전탐색의 방식이기 때문에 시간복잡도를 반드시 확인 해봐야죠. 만약 입력값이 크다면 완전탐색이 아닌 다른 방식의 풀이로 풀라는 의미입니다. 이 문제는 최대 입력값이 100,000이고 각 구간마다 10번씩 탐색하기에 시간초과에는 걸리지 않을거라 판단하고 완전탐색으로 돌렸습니다. 내가 사려고 하는 물품들에 대한 정보는 map로 저장해두고 하나씩 줄이면서 모든 탐색이 끝나고 사려고하는 모든 물품의 갯수가 0보다 작거나 같으면 카운트를 ++해줬습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..

정답을 만들어낼 수 있는 모든 조건의 경우의 수를 다 탐색해보는 문제였습니다. 문제가 길긴 하지만 어려운 부분은 딱히 없고 그대로 구현만 하면되는데, SoloGame 함수의 인자로 cards를 넘길 때 참조로 넘기게 되면 cards의 변화가 계속 반영되기 때문에 참조가 아닌 일반적인 복사 형태로 넘겨야합니다. 그래야 경우의 수마다 서로 다른 cards를 참조해서 정확한 답을 도출할 수 있습니다. 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 #include #inc..

두개의 컨테이너 벨트를 사용해서 주어진 order에 맞게 택배를 담을 수 있게 하는 것이 문제 해결의 요지였습니다. 서브 컨테이너가 마치 자료구조의 Stack과도 같은 구조를 하고 있기 때문에 두 개의 vector를 통해 어렵지 않게 해결이 가능한 문제였습니다. 하나 주의해야할 부분은 서브 컨테이너에 옮기다가 order에 맞게 택배 상자를 실은 다음에, 다음 차례로 실어야 하는 박스 번호가 서브 컨테이너와 메인 컨테이너에서 곧 장 꺼낼 수 없다고 하더라도 더 실을 수 있는 경우가 존재하는 것 입니다. 메인컨테이너가 비어있는게 아니라면 서브컨테이너에 다시 옮기면서 이번에 실어야 하는 박스번호를 찾아서 옮길 수 있는 경우가 존재합니다. 처음 풀이에는 저도 문제에 나와있는 테스트케이스만 보고 그대로 구현하다보..

문제 해결을 위해선 결국 앞에서 부터 topping배열의 끝까지 모든 경우를 다 확인해 봐야 한다고 생각했습니다. 그런데 한번 배열을 자를때마다, 왼쪽 오른쪽 둘다 순회하면서 중복을 제외한 토핑의 가지수를 다 세는 경우에는 시간초과가 날 수 있는 Input 범위입니다( 최대 1,000,000 ). 결국 일일이 다 순회하지 말고 해결하라는 의도가 담겨 있는 문제이지요. 그래서 모든 순회를 하지 않는 선에서 갯수를 셀 수 있는 방법은 사실 map을 사용하는 경우 말고는 떠오르는 것이 없기 때문에 map을 잘 이용할 생각만 떠올린다면 LV2 치고는 쉬운 문제였다고 생각합니다. 아이디어를 떠올리고 나서 코드를 짜는건 5분도 안걸렸습니다. 생각보다 map을 이용해서 해결하는 문제가 많기 때문에 map의 활용은 정..

C++의 컨테이너 중 하나인 map을 알면 쉽게 해결할 수 있는 문제였습니다 ! 체감상 다른 Lv2 문제들 보다는 쉬운 편이었습니다. 따로 함정이 존재하지도 않고 생각한대로 구현해서 바로 맞은 몇 안되는 문제였습니다. map은 key값과 value값을 함께 가질 수 있기 때문에 크기를 key값으로 그리고 그 갯수를 value로 insert 해줍니다. 그러면 map에는 귤의 크기와 그 크기를 가진 갯수가 저장되어있고, 정렬을 위해 vector 컨테이너로 옮겨서 크기별로 내림차순으로 정렬합니다. 그러면 갯수들이 많은 귤의 크기정보순으로 정렬이 되고, 담고자 하는 k에서 맨 앞에서부터 그 크기대로 값을 빼주면서 갯수를 카운팅합니다. 그렇게 0이되거나 0보다 작을때까지 계속 빼주면 서로 다른 종류의 최솟값을 쉽..

처음엔 구조체로 입력에 들어있는 가장 큰 값들을 k의 갯수만큼 인덱스와 함께 넣고, 값들을 0으로 바꾸어서 1라운드부터 진행하는 식으로 했는데 이렇게 하면 큰 오류가 있습니다. k=4라고 가정할때, 3 3 3 3 5 5 5 5 가 입력이면 n이 12가 넘으면 위의 풀이가 정답이 될수 있지만 그게 아니라면 k를 다 뒤에서 써버리는 로직이기 때문에 올바른 답을 도출 할 수가 없습니다. 결국 이 풀이는 틀린 풀이었고 일단 n을 사용해가면서 0보다 작아질때, 지나왔던 곳에서 가장 큰 숫자가 있었던 라운드를 지우는 방법의 풀이가 정답을 받을 수 있었습니다. 이 풀이에서 놓칠 수 있는 부분은 k를 다 사용하기 전에 인덱스가 enemy의 크기를 넘어서는 경우가 있을 수 있어서 마지막에 return enemy.size..