DP(다이나믹 프로그래밍): 백준 9095 파이썬 1,2,3 더하기
문제: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이: 이 문제를 풀면서 어떻게 점화식을 세워야 하는지에 대한 고민을 1시간 정도 했었는데 잘 떠오르지 않아 결국 구글링을 했다. 규칙은 아주 간단했다. 점화식을 찾아서 해결하는 전형적인 DP문제였다. 1 -> (1), 1개 2 -> (1+1), (2) 2개 3 -> (1+1+1), (1+2), (2+1), (3) 4개 4 -> (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), .... 7개 5 -> (1+1+1+1+1), .... 13개 위의 규칙을 봤을 때, 정수 4..
[프로그래머스] 튜플 파이썬
문제: https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이: 입력받은 s를 리스트로 변환한다. 그 이후에는 만들어진 리스트의 요소를 하나씩 접근, answer 리스트에 중복이 되지 않도록 not in 을 사용하여 하나 씩 append 한다. 여기서 핵심은 {{2}, {2,1}, {2,1,3}, {2,1,3,4}} {{2,1,3,4}, {2}, {2,1,3}, {2,1}} {{1,2,3}, {2,1}, {1,2,4,3}, {2}} 일 경우 다 ..
DP(다이나믹 프로그래밍): 백준 15988 파이썬 1,2,3 더하기 3
문제: https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이: 이 문제는 '1,2,3, 더하기 1' 9095번 문제에서 n의 범위가 크게 늘어난 문제이다. 이 문제에 9095번 문제와 같은 코드를 제출하면 메모리 초과가 발생한다. 그래서 다르게 풀어야 하는데, 먼저 다이나믹 프로그래밍 기법으로 범위 내의 방법 수를 다 구해서 리스트 'd'에 모두 저장한 뒤에 각 테스트 케이스를 입력받아 리스트 'arr'에 그 결과를 저장한다. 입력받은 테스트 케이스를 모두 저장하고 있지 않고, 테스트 케이스에 ..
