printf("hellow coding");

https://www.acmicpc.net/problem/2579

이 문제는 DP에서 상당히 유명한 문제입니다. 

solved.ac 에서 책정한 기준으로는 실버 3정도의 난이도이지만.. 제 기준에선 그것보다는 어려웠던것 같습니다. 

여기서는 문제를 풀기위한 점화식을 세우는 것이 까다롭습니다. 

우선 문제의 조건은 아래와 같습니다. 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

위 세가지 조건이 점화식을 세우는 조건입니다.

위 기준에 따라서 처음에 점화식은 쉽게 새울 수 있었습니다.

dp[i]가 'i번째 계단까지 올라오는데 얻을 수 있는 최고의 점수' 라 세우고 점화식을 세우면 아래와 같습니다. 

dp[i] = max( i번째 계단의 값 + i-1번째 계단의 값 + dp[i-3], i번째 계단의 값 + dp[i-2])

위 점화식이 세워진 이유는 아래와 같습니다. 

이와 같이 dp[4], 즉 4번째 계단까지 올라오는데 얻을 수 있는 최고의 점수를 구해봅시다

먼저 1번의 경우를 보겠습니다.

이 경우는 우선 4번째 계단과 3번째 계단의 값을 더합니다. 그렇게 되면 현재 3,4번째 계단이 연속으로 밟혀져 있는 상태가 되므로, 만약 2번째 계단을 밟는 어떠한 경우라도 여기에 포함되게 된다면, 문제의 조건을 위배하게 됩니다. 

따라서 이 경우를 배제하고자, 여기에 dp[i-3]인 dp[1], 즉 1번 계단까지 올라오는데 얻을 수 있는 최고의 값을 더해주는 것입니다. 이렇게 된다면 2번째 계단을 밟는 경우를 배제하고 값을 구한것이므로 문제의 조건을 위배하지 않은 경우의 수를 구할 수 있게 됩니다. 

다음 2번째 경우 입니다. 

이 경우는 4번째 계단을 밟고, 아예 처음부터 연속으로 계단을 밟을 여지를 남기지 않는 경우 입니다. 

즉 dp[i-2] = dp[2] (두번째 계단까지 얻을 수 있는 최고의 값) 에 4번째 계단의 값을 더해준다면 연속으로 계단을 밟는 경우를 모두 배제한 것이므로 조건의 만족하는 경우의 수를 구할 수 있게 됩니다. 

따라서 이 1번과 2번의 값을 계산하고 그 중 큰 값을 비교한다면 , dp[i]의 값을 구할 수 있게 될것입니다.

하지만 주의해야할 점은, i값이 너무 작아 위 점화식의 인덱스를 포함하지 못하는 경우들 ,

즉 dp[0],dp[1],dp[2]에 대해서는 따로 점화식을 구하여 값을 입력해 주어야 합니다.. 

이 값은 dp[0] == 0 , dp[1] == 첫번째 계단의 값 , 그리고 dp[2] = max(1번,2번계단의 합, 1번 계단의 값) 

으로 설정할 수 있습니다.

따라서 위 알고리즘을 토대로 코드를 구현하면 다음과 같습니다.

n = int(input()) stair = [int(input()) for _ in range(n)] dp = [0 for _ in range(n+1)] def solve(): for i in range(n+1): if i == 0: continue elif i ==1: dp[i] = stair[i-1] elif i ==2: dp[i]= max(stair[i-1]+stair[i-2], dp[i-1]) else: dp[i] = max(stair[i-1]+stair[i-2]+dp[i-3],stair[i-1]+dp[i-2]) print(dp[-1]) solve()

https://www.acmicpc.net/problem/11726

이 문제는 앞에서 포스트 했던 '이친수' 문제와 상당히 유사합니다. 

경우의 수를 나열해 보아도 쉽게 규칙이 보이지만, 이론적으로 생각해 보아도 쉽게 규칙을 발견할 수 있습니다. 

위 그림은 i = 5 일 때의 예시입니다. 

따라서 이와 같은 알고리즘을 코드로 구현하면 쉽게 풀이가 가능합니다. 

#타일 2xn n = int(input()) dp = [0 for _ in range(n+1)] for i in range(n+1): if i == 0: dp[i] = 0 continue elif i==1 or i==2: dp[i] = i else: dp[i] = dp[i-2]+ dp[i-1] print(dp[n]%10007)

https://www.acmicpc.net/problem/15664

유명한 N과 M 시리즈이다. 

이 문제는 앞에서 포스트한 N과 M(8)번 문제의 연장선이다.

이 문제에서 중요한건 dfs를 이용하여 필요한 경우의 수를 탐색한 후 결과값으로 출력하는 것이다 

즉, 핵심 알고리즘 부분은 for문에서 index 범위를 지정하여 탐색하는 부분이라 할 수 있다. 

우선 코드는 다음과 같다. 

# 엔과 엠 (10) n,m = map(int,input().split(' ')) number = list(map(int,input().split(' '))) number.sort() array = [] result = [] def solve(level, index): if level == m: a= ' '.join(map(str,array)) if a not in result: result.append(a) print(a) return for i in range(index, n): #핵심 부분 array.append(number[i]) solve(level+1, i+1) array.pop() solve(0,0)

앞서 포스트한 N & M(8)서는

solve(level+1, idx) -> 탐색을 하고 해당 idx를 넘어가지 않고 그대로 input으로 두어 탐색할 수 있게 하였다면 

이번 포스트에서는 solve(level+1,idx+1) 로 지정하여 한번 탐색한 경우는 다시 고려하지 않고 넘어가는 식으로 구현하는것이 차이라고 볼 수 있다. 처음에 풀때 input 문자열을 굳이 int형으로 지정하여 문제를 풀었었는데 그럴필요없이 str 자료형으로 문제를 해결하면 될듯하다. 

https://www.acmicpc.net/problem/2193

이 문제는 '타일' 문제와 비슷하다 

시작은 무조건 1로 시작해야하며, 11이 두 번 연속으로 나타나지 않는 이진수를 찾는 문제이다.

그냥 경우의 수를 나열해 봐도 쉽게 규칙을 찾을 수 있지만 

조금만 생각해보면 알고리즘을 금방 생각할 수 있다. 

만약 4자리 이친수의 갯수를 찾는다하면 (dp[4]라고 하자) 

dp[3](3자리 이친수) 에다 마지막에 '0'을 하나 붙여도 이친수를 만족하며

dp[2](2자리 이친수) 에다 앞에 '10'을 붙여도 위 두 조건을 만족한다 

따라서 규칙은 dp[i] = dp[i-1]+dp[i-2]임을 알 수 있다. 

코드는 아래와 같다.

n = int(input()) dp = [0, 1, 1] for i in range(3, n+1): dp.append(dp[i-1]+dp[i-2]) print(dp[-1])

https://www.acmicpc.net/problem/8595

이 문제는 사실 알고리즘이 특별하다기보다 구현하는데 있어서 조금 생각이 필요했던 문제였습니다. 

어설프게 for문을 여러번 돌릴경우에 시간초과가 나기 때문에, 주어진 문자열을 for문 한번에 돌려 

해답을 찾아내는 구현을 하는것이 관건입니다.

이를 위해서 앞에서 부터 문자열을 탐색하는 것이 아닌 뒤에서 부터 문자열을 탐색하여

숫자가 하나씩 나올 때마다 (자리수) * 해당숫자, 즉 처음 나온 숫자라면 1*(해당 숫자) 

두번째 연속으로 나온 숫자라면 10*(해당숫자), 이런 식으로 탐색하여 더해주는것이 해답입니다. 

코드는 아래와 같습니다.

import sys n = int(input()) word = input() number = [str(i) for i in range(10)] def solve(): jump = 1 result = 0 temp = 0 for i in range(n): i = -i -1 if word[i] in number: temp += int(word[i])*jump jump = 10*jump if i ==-n or word[i] not in number: if jump >= 10000000: #숫자가 6자리 이상이라면 종료, jump = 1 temp = 0 continue result += temp jump = 1 temp = 0 print(result) solve()

https://www.acmicpc.net/problem/15657

이번 문제는 장장 1시간 가까이 삽질을 한 문제입니다.. 

알고리즘 자체는 dfs를 잘 알고 있다면 무난하게 풀 수 있는 문제입니다. 

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다

이 3가지 조건중에서 3번째 조건은 맨처음 받은 입력을 정렬만 해주면 해결되는 문제이고,

첫번째 M개를 고른다는 조건은 dfs에서 level M 까지 탐색하고 종료한다는 뜻 

두번 째 같은 수를 여러 번 골라도 된다 라는 조건은 알고리즘 적인 코딩을 통해 해결할 수 있습니다. 

그에 따라 작성한  코드는 다음과 같습니다. (주의!  틀린부분이 있습니다.)  

n,m = map(int, input().split(' ')) number = input().split(' ') number.sort() array = [] def dfs(level, index): if level == m: print(' '.join(result)) return for i in range(index,n): array.append(number[i]) dfs(leve+1, i) # 같은수를 여러번 뽑을 수 있으니까 i번을 넣음, # 여러번 뽑을 수 없다면 i+1을 넣음 array.pop(-1) #또다른 경우를 넣어주기위해 기존의 경우를 pop

위에서 틀린 부분 눈치채셨나요?

이 코드를 작성할 때 입력을 한자리수 숫자로 가정하고 작성하였습니다.. 

한자리 수일 때는 문제가 없지만 만약 숫자가 한자리수 이상일 경우에는 

문자열로 받을경우 1234 -> '1','2','3','4' 로 받게 되기 때문에 기존의 생각한 것과 다른결과를 얻게됩니다..

저는 이 부분을 생각을 못해 1시간 동안 오류를 찾는데 시간을 보냈습니다..

수정한 코드는 아래와 같습니다. 

n, m = map(int, input().split(' ')) number = list(map(int, input().split(' '))) number.sort() array = [] def dfs(level, index): if level == m: print(' '.join(map(str, array))) return for i in range(index, n): array.append(number[i]) dfs(level+1,i) array.pop() dfs(0,0)

https://www.acmicpc.net/problem/1256

개인적으로 사고 과정이 복잡하고 더러..운..? 문제였던것 같습니다.. 

우선 코드만 첨부하고 설명은 다음에 업로드하도록 하겠습니다.

이 문제는 메모리 용량과 시간을 잘보고 구현해야 하는데요.. 저는 이차원배열로 모든 조합 경우의 수를 

규칙에 따라 미리 저장하고 문제를 해결하였는데, 메모리 용량 초과로 결국 combination과 factorial함수를 다시 따로 구현해야 했습니다..  

n, m, k = list(map(int, input().split(' '))) N = n+m dp = [1] * (N+1) def factorial(N): if N==1 or N==0: dp[N] = 1 return 1; else: val = N * factorial(N-1); dp[N] = val return val def binomial(n1, n2, facto): return (facto[n1+n2]) / (facto[n1] * facto[n2]) def find_k(n, m, k, string, facto): if n==0: for _ in range(m): string.append('z') elif m==0: for _ in range(n): string.append('a') else: case = binomial(n-1, m, facto) if case < k: string.append('z') find_k(n, m-1, k-case, string, facto) elif case >= k: string.append('a') find_k(n-1, m, k, string, facto) return string factorial(N) answer_string = [] string = find_k(n, m, k, answer_string, dp) if k > binomial(n, m, dp): print(-1) else: for i in range(len(string)): print(string[i], end='')

https://www.acmicpc.net/problem/1937

이번 문제는 구현을 생각하는데 있어서 까다로웠던 문제였습니다. 

일단 그래프를 탐색하는데 있어서 dfs를 재귀적으로 구현, 또 탐색에 조건문을 달고, dp의 메모이제이션을 이용하여 연산 케이스 감소 등 3개의 콤비네이션을 이용한 구현이 필요했는데요.. 처음 구상한 주도 코드는 다음과 같습니다

어차피 조건에 항상 더 큰 숫자가 있는곳으로만 이동한다 하였으니, 다시 같은곳으로 되돌아오게될 경우를 

체크할 필요는 없습니다. 다만 문제에 주어진 조건을 잘 정의하고, 해당하지 않는경우는 pass, 

그리고 dfs로 탐색하게 될경우 재귀적으로 반환값을 받아 차례대로 각 이동경로마다의 best값을 설정하게 해주는 부분이 생각하기 까다로웠던것 같습니다.  

위 주도코드를 기반으로 작성한 코드는 다음과 같습니다. 

import sys n = int(input()) forest = [list(map(int, input().split(' '))) for _ in range(n)] dp = [[-1 for _ in range(n)] for _ in range(n)] direct = [(0,1),(0,-1), (1,0), (-1,0)] sys.setrecursionlimit(1000000) #중요, 선언하지 않으면 런타임 에러.. def dfs(i,j): if dp[i][j] != -1: return dp[i][j] else: dp[i][j] = 1 for k in direct: mv = tuple(sum(elem) for elem in zip((i,j), k)) if mv[0] <0 or mv[0]>=n or mv[1] <0 or mv[1]>=n or forest[i][j] >= forest[mv[0]][mv[1]]: continue else: dp[i][j] = max(dp[i][j], dfs(mv[0],mv[1])+1 ) return dp[i][j] def solve(): best = 0 for i in range(n): for j in range(n): best = max(best, dfs(i,j)) print(best) solve()

여기에서 중요한 부분은 sys.setrecursionlimit(1000000) 를 선언해주는 것이었는데요..

파이썬에서는 재귀적 탐색할 경우 탐색할 수 있는 깊이가 제한되어있어서 이렇게 리미트를 해제해야 합니다 

또한 dp[i][j]가 기본적으로 어떠한 값이 설정되어있다면, 그 값을 return하게 하여 불필요한 탐색경우를 줄였습니다. 

이상으로 욕심쟁이 판다 포스트를 마치겠습니다.