목록전체 글 (139)

jae_coding

(백준 알고리즘 문제풀이) 10057번 오르막 수

문제 문제 링크 문제 접근 비트 마스킹을 통해서 문제를 풀어봐야겠다. 이 문제 또한 문제의 패턴을 잘 파악해야 한다. 내가 생각한 패턴은 표와 같이 생각을 해보았다. A[n][0] = 1, 일반화 공식: A[n][m] = A[n-1][m] + A[n][m-1] 0 1 2 3 4 5 6 7 8 9 1자리 1 1 1 1 1 1 1 1 1 1 2자리 1 1 + 1 = 2 2 + 1 = 3 4 5 6 7 8 9 10 3자리 1 3 6 10 15 21 28 36 45 55 코드 import sys N = int(sys.stdin.readline()) lst = list([1] + [0] * 9 for _ in range(N)) lst[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in..
알고리즘 문제/백준 2022. 7. 5. 21:43
(백준 알고리즘 문제풀이) 1010번 다리 놓기

문제 문제 링크 문제 접근 N에서 M으로 가는 경우의 수를 구하는 것이다. N이 M보다 작거나 같으므로 조합공식 mCn을 적용시킨다. 코드 import sys def factorial(N): result = 1 for i in range(1, N+1): result *= i return result T = int(sys.stdin.readline()) for _ in range(T): N, M = map(int, sys.stdin.readline().split()) # M >= N # Combination ans = int(factorial(M) / (factorial(N) * factorial(M-N))) print(ans) 느낀점 조합에 대한 공식을 도출하는데까지의 시간이 좀 걸린 것 같다.
알고리즘 문제/백준 2022. 7. 5. 20:39
(백준 알고리즘 문제풀이) 2193번 이친수

문제 문제 링크 문제 접근 dp 문제이자 일반식을 도출해내는 문제인 것 같아서 바로 접근을 시도해보았다. An이 피보나치 수열과 동일하다는 일반화를 공식화해내었다. An = A(n-2) + A(n-1), n >= 2일 때의 일반식을 도출해냈다. 코드 import sys def fib(N, memo): if N == 1 or N == 2: return 1 elif N not in memo: temp = fib(N-2, memo) + fib(N-1, memo) memo[N] = temp return memo[N] else: return memo[N] memo = dict() N = int(sys.stdin.readline()) print(fib(N, memo)) 느낀점 피보나치 수열을 알고있고, 일반식에 대..
알고리즘 문제/백준 2022. 7. 5. 20:00
Prev 1 ··· 42 43 44 45 46 47 Next