궤도

문제 풀이 주어진 예제 입력이 하나인데다가 대충 생각해도 알 수 있는거라 좀 힘들었다. N의 입력이 무조건 짝수인 것만 계산했지 홀수인 경우에 0을 리턴해야 한다는 생각을 못해서 틀리기도 했고... dp배열엔 N/2를 저장할 것이다. 그니까 N=2면 dp[1]에 그 답이 있고, N=4면 dp[2]에 답이 있다. 아무튼 N=2일 때 타일을 채우는 방법은 다음과 같다. N=4라면 일단 처음 3x2를 N=2일 때처럼 채우고, 그 뒤는 dp[1]을 호출하면 된다. 이런식으로... 그럼 여기서 3*dp[1]이 된다. 근데 다른 방법으로도 타일을 채울 수 있다. 이런 모양이 2종류가 있다. 그럼 2*dp[0]을 하면 되는건가?? 여기서 N=6일때로 가면... 이런 것도 가능하고 이런 것도 가능하다. 그럼 dp[i]..

문제 풀이 dp는 점화식을 세우는게 제일 어렵다... 처음엔 2차원 dp배열을 선언해서 세로가 N(i)일 때 사자 j마리를 넣는다면...식으로 생각했지만, 나눠지는 경우의 수가 너무 많았다. dp인데 경우의 수가 일관적이지 않게 나눠진다면 뭔가 잘못하고 있단 뜻이니 바로 방향을 틀어야 한다... 그래서 i번째 줄에 집중하기로 했다. i번째 줄에서 가능한 경우는 3개가 있다. 1. 사자가 없다. 2. 왼쪽에 사자가 있다. 3. 오른쪽에 사자가 있다. 1번의 경우엔 i-1번째 줄에서 사자가 없든 어디에 있든 상관없다. 2번의 경우엔 i-1번째 줄에서 사자가 없거나 오른쪽에만 있어야 한다. 3번의 경우엔 i-1번째 줄에서 사자가 없거나 왼쪽에만 있어야 한다. 정리하자면 dp[100000][3]일 때 dp[i]..

문제 풀이 1년 반전에 자료구조 시간에 이미 배운 문제라...풀이 방법도 그때에서 전혀 달라지지 않았다. 이게 정석이기도 하구 스택에 연산자를 쌓다가 적절한 때에 출력하는게 중요한데, 여기에 연산자 우선순위를 사용한다. 다들 알겠지만 연산자의 우선순위는 괄호, 곱셈나눗셈, 덧셈뺄셈이다. 그리고 스택에 연산자를 쌓을 건데 절대로 나보다 우선순위가 높거나 같은 연산자 위에 쌓일 수는 없다. 그니까 곱셈이 이미 스택에 들어온 상태에서 덧셈이 들어오려 한다면 곱셈이 스택에서 나와야 한단 것이다. 피연산자인 A~Z는 스택에 쌓이지 않는다. 그냥 간단히 말해서 우선순위가 그 어떤 연산자보다 높다고 생각하는게 맘 편할 수도 있겠다. 그래서 이 2가지 규칙 1. 스택에 쌓이는건 오직 연산자 2. 나보다 우선순위가 높은..

문제 풀이 이 문제의 핵심은 커서 위치 정보를 따로 저장하지 않은 채 문제를 푸는 것이다. 그러려면 스택을 2개 사용해야 한다. s1에 입력을 char 단위로 쪼개어 넣었다. 커서는 처음에 문장 맨 뒤에 위치한다. 이때 커서의 왼쪽 문자는 d고 이는 s1.top과 일치한다. 그럼 각 명령에 대해 해야할 일은 무엇일까? L d를 가리키던 커서가 c를 가리키도록 해야한다. s1.top이 c가 되기 위해선 d가 없어져야 한다. 하지만 d를 완전히 없앨 수는 없다. 그래서 d를 s2에 옮겨준다. D c를 가리키던 커서가 다시 d를 가리키도록 해야한다. 그럼 s1.top이 다시 d가 되어야 한다는 것이다. s2.top에 있던 d를 다시 s1으로 옮겨온다. B 현재 커서의 왼쪽 문자를 지워야 한다. 이는 s1.to..

문제 풀이 이 문제를 풀기 위해선 2차원 dp배열을 사용해야 한다. dp[i][j]를 0부터 j까지의 정수 i개를 더해서 그 합이 j가 되는 경우의 수라고 하자. 쉽게하기 위해 N=4, K=3이라고 하자. 0 1 2 3 4 1 1 1 1 1 1 2 1 3 1 먼저 K=1인 경우 dp[1][j]=1일 것이다. 0부터 j까지의 정수 1개를 더해서 그 합이 j가 되는 경우의 수는 j 스스로를 사용하는 경우 1개 뿐이기 때문이다. 다음으로 N=0인 경우 dp[i][0]=1일 것이다. 몇개의 숫자를 사용한들 그 합이 0이 되기 위해선 0만을 i개 더하는 경우 1개 뿐이기 때문이다. 그렇다면 K=2, N=1인 경우를 보자. 0부터 1까지의 정수 2개를 더해서 그 합이 1이 되어야 한다. 그 합을 a+b+c+d+e...

문제 풀이 myunji.tistory.com/319?category=1154147 [백준] 11052번 : 카드 구매하기 문제 풀이 문제를 풀고 다른 이들의 코드를 찾아봤는데, 다들 범위처리를 나와 다르게 했다. 근데 내가 더 효율적인 것 같고...이렇게 해도 될 것 같기도 하고 그리고 일단 AC를 받았기 때문에 내 myunji.tistory.com 이 문제랑 결이 비슷한 것같다. 32를 제곱수의 합으로 나타낸다고 해보자. 일단 6^2 = 36으로 32보다 크기때문에 6을 쓸 순 없다. 그럼 5^2을 쓰면? 32-25니까 7이 남는다. 예제 입력 1을 보면 알겠지만 7을 표현하는 제곱수 항의 최소 개수는 4다. 그렇기 때문에 5^2를 사용하면 4+1 = 5가 될 것이다. 4^2를 써보도록 하겠다. 32-..

문제 풀이 myunji.tistory.com/217 [백준] 1912번 : 연속합 문제 풀이 이것도 유명한 동적계획법 문제인데... 그냥 뭐 간단하게 생각해서 이런 수열이 있다고 하자 5, -8, 9, -1, ... 당연히 처음은 0으로 시작할 것이다. 0+5를 해서 5가 나왔고 다음 숫자를 보니 myunji.tistory.com 이 문제에서 숫자를 하나 삭제할 수 있게 됐다. 그래서 del_sum이란 변수를 하나 추가한다. del_sum은 숫자를 삭제했을 수도 아닐 수도 있다. 특정 input이 들어왔을 때 del_sum에 들어올 수 있는 경우는 2가지다. 이 input을 사용하거나 삭제하거나. input을 사용할 때는 del_sum = del_sum+input이다. input을 버릴 땐 del_sum..

문제 풀이 내가 원래 LIS를 풀던 방식으로 풀려다가 엄청난 삽질을 했다. myunji.tistory.com/214 [백준] 11053번 : 가장 긴 증가하는 부분 수열 문제 풀이 대표적인 동적계획법 문제이다. 증가하는 부분 수열을 담은 max_num이란 배열이 있다고 하자. max_num의 상태는 다음과 같다. 10 20 30 현재 max_num의 길이는 3이니 가장 긴 증가하는 부분 수 myunji.tistory.com 이게 내가 원래 LIS를 풀던 방식... 이 문제에선 dp에 최장 길이를 저장할 필요가 없다. 우리가 찾는건 가장 큰 수열의 합이기 때문이다. 그래서 O(n^2)의 시간복잡도로 진행을 할 것이다. 말로 설명하면 어려우니 데이터로 설명하겠다. 1 100 2 50 20 60 3 5 의 데..