DP3 백준4655🐨Hangover https://www.acmicpc.net/problem/4655Hangover (브론즈 III)문제어떻게 카드로 쌓아 만든 탑이 테이블을 얼마나 멀리까지 돌출하게 만들 수 있을까?1장의 카드로는 최대 절반(1/2) 카드 길이만큼 돌출할 수 있다.(카드는 테이블에 수직으로 세워진다고 가정한다.)2장의 카드를 사용하면:첫 번째 카드가 두 번째 카드 위로 1/2 길이만큼 돌출한다.두 번째 카드가 테이블 위로 1/3 길이만큼 돌출한다.총 돌출 길이는 ( 1/2 + 1/3 = 5/6 ) 카드 길이이다.일반적으로 n장의 카드를 사용하면 ( 1/2 + 1/3 + 1/4 + … + 1/(n + 1) ) 카드 길이만큼 돌출할 수 있다.위쪽 카드부터 두 번째 카드를 1/2, 두 번째 카드는 세 번째 카드 위로 1/3, .. 2024. 10. 14. # 9251번 LCS def lcs(A, B): lenA, lenB = len(A), len(B) DP = [[0] * (lenB+1) for _ in range(lenA+1)] for i in range(1, lenA+1): for j in range(1, lenB+1): if A[i-1] == B[j-1]: DP[i][j] = DP[i-1][j-1] + 1 else: DP[i][j] = max(DP[i-1][j], DP[i][j-1]) return DP[lenA][lenB] def main(): A = input() B = input() print(lcs(A, B)) if __name__ == "__main__": main() lcs(A, B) 함수는 두 문자열 A와 B를 입력으로 받습니다. 변수 lenA와 lenB는 각.. 2024. 2. 19. 백준1003🐨피보나치 함수.py - DP, MEMO + 분할 정복 1003번: 피보나치 함수각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.www.acmicpc.net와 피보나치다! CPP 코드도 줬네? 전역변수 써서 더하면 되잖아 하고 풀다가 뭔가 이상함을 감지했습니다. 게다가 라이브러리 문제로 컴파일 에러도 났습니다. 나중에 의도대로 수정해 보니 역시 시간초과입니다.#include int zeros, ones;int fibonacci(int n) { if (n == 0) { zeros++;return 0;} else if (n == 1) {ones++;return 1;} else {return fibonacci(n - 1) + fibonacci(n - 2);}}int main() { int number.. 2024. 2. 2. 이전 1 다음
