` dp문제
위치, 현재 높이(now), 이전 높이(before) 로 3차원 배열 2개 모든 경우를 구한 것과 2높이가 없는 경우를 구해 차이를 구함 현재 높이와 과거 높이를 보고 다음에 올 수 있는 높이의 경우를 구하는 식임
처음에 java로 풀었는데 시간초과 떠서 python으로 하니 통과됐다.
`
예시에서 8 12 -> 16
8과 12의 최대공약수는 4이고 최대공약수로 나눈 타일에서 대각선 포함 타일 * 최대공약수를 해주면 됨.
n과 m이 서로소일 경우 n이 크든 m이 크든 상관 없이 n+m-1개의 타일 개수가 포함되는 것을 알 수 있었음.
python 풀이
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 def sol(n, now, before): global MOD_NUM if n == 0: // 처음에 시작 높이 1 if now == 0: dp[n][now][before] = 1 else: dp[n][now][before] = 0 return dp[n][now][before] if dp[n][now][before] == -1: a1, a2, a3 = 0, 0, 0 // 높이가 0일 경우 다음꺼 상관x if now == 0: a1 = sol(n - 1, 0, now)% MOD_NUM a2 = sol(n - 1, 1, now)% MOD_NUM a3 = sol(n - 1, 2, now)% MOD_NUM elif now == 1: //현재 1 if before == 0: // 이전 높이가 0이면 아무거나 올 수 있다.
` graph 문제
처음에 그래프를 만드는 식으로 하려 했으나 a->b, a->c는 불가능하고 a->c, b->c는 가능하다.
따라서 각 알파벳에 대해 부모를 지정해주면 배열로 처리할 수 있음.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import java.
` brute force + Backtracking
처음에 에라토스테네스의 체로 문제를 풀었고 역시나 메모리 초과가 떠서 소수 판별 방식 재구성 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 import java.
` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.
`
홀수는 n +(n+1)로 표현가능 짝수의 경우 다음과 같이 생각할 수 있다. $6 = 2+2+2$ 에서 앞 뒤로 1을 빼고 더하면 $1+2+3$ $14 = 2*7 = (-1+0+1)+2+3+4+5 = 2+3+4+5$ 그렇다면 12인 경우 답은 3+4+5인데 2+2+2+2+2+2에서 위와 같이 하긴 힘들다.
` dfs 문제
min과 max를 구해 E가 범위 안에 있기만 하면 답을 바로 구할 수 있음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 import java.