지금은마라톤중

실패한 접근법- matrix를 그리고 반복문을 통해 구현→ 시간초과로 실패import sysinput = sys.stdin.readlinen, m = map(int,input().split())matrix = [list(map(int,input().split())) for _ in range(n)]for _ in range(m): result = 0 x1,y1, x2,y2 = map(int, input().split()) for i in range(y1, y2+1): if x1 == x2 : result += matrix[i-1][x1-1] else: result += sum(matrix[i-1][x1-..

접근법- 메모리제이션 활용- (이전의 최대값 + 현재값)과 현재값 비교하며 최대값 결정 n = int(input())lst = list(map(int, input().split()))dp = [0] *(n+1)for i in range(1,n+1): dp[i] = max(dp[i-1]+ lst[i-1], lst[i-1])print(max(dp[1:]))

하루를 마무리하며 하나 풀어봅니다. 접근법- DP- 점화식 : dp[i] = dp[i-2] + dp[i-1] 실패 코드 - 입력값의 범위를 모두 충족하지 못했습니다. - n = 1일때 dp[2]에서 index out of range 에러 발생n = int(input())dp = [0 for _ in range(n+1)]dp[1], dp[2] = 1,2for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2]print(dp[n]%10007) 정답 코드n = int(input())dp = [0 for _ in range(n+1)]if n

제곱수의 합들을 구해보면 다음과 같습니다.1 : 12: 1 + 13: 1 + 1 + 14: 45: 4 + 16: 4 + 1 + 17: 4 + 1 + 1 + 18: 4 + 49 : 910: 9 + 111: 9 + 1 + 112: 4 + 4 + 4 시도 : 실패- 재귀함수 사용- N보다 작거나 같은 제곱수를 빼면서 카운팅- 반례 존재 : 12( 9+1+1+1)로 나오지만 최소개수는 3개(4+4+4)- 시도방법은 최소개수가 아닌 단순히 제곱수들의 합으로 나타내기만 한 것import syssys.setrecursionlimit(100000)def cal_func(n, cnt): num = int(n**0.5) rest = n - (num**2) cnt +=1 if rest == 0 : ..

DP 문제가 익숙해질 때까지 난이도를 올려가면 문제를 풀어보려고 합니다.해당 문제는 규칙성을 찾았다고 생각했는데 올바른 접근법이 아니여서 시간이 걸렸습니다. 시도- 안 되는 경우의 수를 찾기- 전체 경우의 수 - 안되는 경우의 수→ 안 되는 경우의 수가 1,2,3,6,10..... 나름의 규칙성을 가졌다고 생각해서 접근법을 가졌다고 생각했으나 틀렸다.  올바른 접근법- 각 자리에 대한 경우를 쪼개서 생각- 자리수가 늘어날때마다 각 숫자의 경우의 수를 생각하여 합하여 값 산출- 일반적 경우 : 2~8은 다음 자리에 올 수 있는 경우가 2가지(이전 자리의 단계수의 경우의 수)- 특수한 경우 : 0,9는 연속된 숫자가 1개임으로 각각 1가지 경우만 존재- dp를 2차원 배열로 만든다( n자리수, n 자리에 올..

해당 문제는 DP 문제입니다. 접근법- 규칙성 찾기- 점화식 형태 구현- 조건을 만족하려면 100, 101 형태를 지켜야함. 1 : 12: 103 : 100, 1014 : 1000, 1001, 10105 : 10000, 10001, 10010, 10100, 10101→ 점화식 : dp[i] = dp[i-1] + dp[i-2]  n = int(input())dp = [0] *(n+1)dp[1] = 1for i in range(2,n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n])

해당 문제는 DP 문제 입니다. 접근법- 작은 문제로 나눴을 때 이번 값을 중복해서 사용할 수 있음- 메모리제이션 활용- 이전 dp를 활용하여 값 계산- 3과 2로 나누어 떨어질 경우 : 최솟값 계산      1) 이전 dp 활용      2) 3과 2로 나누어지는 dp 활용 연산 조건를 한번 더 생각해 볼 필요가 있었습니다.연산 조건의 우선순위를 다시 생각해봤으면 좀 더 빠른 풀이가 가능했을 것 같습니다. x = int(input())dp = [0] * (x+1)def func_dp(n): for i in range(2,n+1): dp[i] = dp[i-1] + 1 if i % 3 ==0: dp[i] = min(dp[i], dp[i//3]..

사실 이 문제를 계기로 DP를 먼저 공부하기로 마음 먹었던 것입니다. 풀다가 6개 실패했습니다..알고보니 DP 알고리즘으로 푸는 문제였습니다. ㅎㅎ 그래서 지난 포스팅에서 DP를 푸는 이론을 먼저 공부하고 다시 도전하게 되었습니다. 접근법 - DP - 최댓값을 가지게 하는 방법 - 1,2번 계산을 무조건 밟는다 - 3번 계산부터 마지막 계산까지는 1칸 or 2칸을 이동 - i 번째 칸 일때 가능한 경우는 1) i-2칸에서 오는 경우와 2) i-3칸에서 i-1로 이동하여 오는 경우 *3칸을 연속해서 이동하지 못하는 점 고려 n = int(input()) scores = [0] scores += [int(input()) for _ in range(n)] dp = [0 for _ in range(n+1)] d..