📑 문제🌱 아이디어입력되는 나무의 양(N)은 1 ≤ N ≤ 1,000,000, 즉 O(n^2)을 가지는 알고리즘이 아닌  O(N)또는 더 빠른 알고리즘을 사용해야 한다. 만약 M미터의 나무를 가져가기 위해서 1~1,000,000까지의 높이를 나이브하게 대입하면서 답을 구할 수 있지만,최악일 경우는 시간초과가 나게 된다. 즉 모든 경우를 대입하는 방식은 이 문제에서는 틀리다! 큰 범위에서 해당값을 하나를 구해야 한다, 이진탐색(Binary Search)을 통해서 해당값을 구할 수 있다. 가정을 해보자, 만약 1 ~ 7까지에서 6을 구해야 한다면 이진탐색은 이렇게 작동한다. 일단 이진탐색을 하기 위해선 최솟값, 중간값(mid), 최댓값을 구해야 한다.처음에는 중간값인 4를 탐색한다, 하지만 답인 "6"이..

📑 문제🌱 아이디어문제에서 여러 가지의 경로를 제공하면 재귀함수를 사용해서 풀 수 있다 전에 재귀함수를 공부하면서 가장 어려웠던 점이 재귀적 사고방식이었다, 이해하기도 전에 "여러 가지 선택지가 있으면 재귀함수도 고려해 보자"라는 생각을 박아 놨던 것 같다. 처음 노드에서 조건 1을 실행하고 조건 1-1에서 결과값이 B가 될 수 없다면 return 하고 전 노드로 되돌아가 조건 1-2를 선택하게 된다. 본문에서 "가능한 연산은 두 가지" 라고 제시했다. 즉 우리는 "2*A"를 선택할 때와 "A*10 +1"을 선택할 때를 재귀적으로 호출하면 된다!두 가지 경우를 만들어 놓는다면 나머지는 컴퓨터가 알아서 해줄 것이다. 🌱 코드 및 풀이sum = 10억 일 때 조건 2를 연산하면 정수형 범위를 벗어나게..

📑 문제🌱 아이디어이 문제는 한 블록당 숫자를 기준으로 푸는 것이 아닌 평탄화 기준이 될 땅 높이를 기준으로 탐색한다! 처음엔 문제에서 말한 조건 1,2번을 DFS로 풀어서 한 블록을 기준으로 평탄화 작업을 하려고 했는데...안된다는 것을 빨리 깨달았다... 이 문제는 "땅의 높이는 256블럭 보다 작거나 같은 자연수 또는 0 이다"  라는 말을 이용해서 풀어야 한다 예를 들어 결국 평탄화 작업을 통해 나오는 땅의 높이는 0 ~ 256까지의 경우가 있다.즉 우리는 0~256까지 경우의 평탄화 기준 땅높이를 토대로 조건 1,2번과 인벤토리를 통해 평탄화할 수 있는지판단하고 평탄화 가능 하다면 최소 시간을 구해야 한다! 주석을 통해 코드마다 설명을 남겨놨으니 천천히 보면 이해하는데 어렵지 않을 것이다.?..

📑  문제🌱 아이디어사자는 마주 보게 배치하면 안 되며, 한 마리도 존재하지 않는 경우도 하나의 경우의 수로 센다 동적계획법(DP)을 사용하면 시간도 아끼면서 풀 수 있다!사실 본인도 점화식 세우는 법을 잘 모른다... 하지만 감이 안 잡히면 N의 수만큼 경우의 수의 수열을 만들어 보자!일단 문제처럼  N*2 배열을 만들어보자! (문제 조건에 성립하는 경우의 수)N = 0 -> 1 N = 1 ->  3N = 2 -> 7N = 3 -> 17N = 4 -> 41 이렇게 증가되는 수열이 만들어진다 이것을 점화식으로 세운다면점화식 = fn = f(n-1)*2 + f(n-2) 이렇게 세울 수 있다. 즉 전값*2 + 전전값 이 현재값이다 이용해서 구현해 보자!🌱  코드 및 풀이점화식을 세우고 DP 통해 구현한..

📑 문제🌱 아이디어본문에서 "다리는 서로 겹칠 수 없다." 라는 조건이 하나 붙는데 이번 문제의 키 포인트이다."다리는 서로 겹칠 수 없다." 라는 말은 곧 순서를 고려하지 않는다 는 말과 같다.두 그림은 같은 사이트에 다리를 잇는 경우의 수이다. 순서를 고려한다면 두 경우는 서로 다른 경우가 되어야 한다.A, B, C != A, C, B 이 경우는 순서를 고려하기 때문에 요소가 같아도 순서가 달라 서로 다른 경우이다. 하지만 문제 조건 중 "다리는 서로 겹칠 수 없다." 를 성립하려면 위 두 그림은 같은 경우의 수가 되어야 한다!중복을 제거해야 하기 때문이다. 즉 A, B, C == A, C, B 이 성립되어야 중복이 제거가 되며 하나의 경우로 본다. 이 문제는 M개에서 N개를 뽑고 중복을 제거해야..