LeeA0의 공부 일기

오랫만에 알고리즘 문제 풀이를 적어보겠습니다~ DP는 풀면 풀수록 어려운데, 특히 이번 문제는 생각치도 못했던 방법이어서 안잊도록 적어보려해요! 오늘의 문제는 N으로 표현입니다. 문제분석 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하..

안녕하세요~ 오늘은 BOJ 1024 수열의 합에 대한 문제 풀이를 적겠습니다. 문제분석 N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성 입력 조건 $N\leq1,000,000,000$, $2 \geq L \geq 100$ 출력 조건 리스트의 길이 $\leq$ 100이면 첫째 줄에 공백으로 구분하여 출력 리스트의 길이가 100보다 크거나 그러한 수열이 없을 때는 -1출력 => 합이 N이고, 길이가 L이상인 연속된 수열을 구한다. (음이 아닌 정수라는게 중요하다.. 0포함!) 풀이방법 N이 1일 때, 2일 때, .... 경우의 수를 나열한 표이다. N 수열 N 수열 N 수열 N 수열 1 0 1 6 1 2 3 0 1 2 3 11 5 ..

안녕하세요! 오늘은 BOJ 1011 Fly me to the Alpha Centauri에 대한 저의 풀이 방법을 적어볼까합니다. 문제분석 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. ) y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다. x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 ..

안녕하세요. BOJ 1004 어린왕자를 풀어봤습니다. 문제 분석 은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자.(행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다.또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.) => 최대한 원의 경계를 관통하지 않으면서 출발점에서 도착점으로 이동한다. 풀이 방법 행성이 하나만 있다고 가정했을 때 출발점과 도착점의 경우의 수는 다음과 같다. 1) 행성을 한 번도 통과하지 않고 갈 수 있다. 2) 도착점에 가기 위해선 반드시 행성을 한 번 진입해야 한다. 3) 1번과 마찬가지로 행성을 한 번도 통과하지 않고 갈 수 있다. 4) 도착점에 가기 ..