백준 9461 파이썬 - 파도반 수열 - 동적 계획법
https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 피보나치와 비슷하게 규칙이 있는 파도반 수열의 N번째 값을 구하는 알고리즘 문제입니다. 위의 그림을 보면 알 수 있듯이... 정삼각형의 변을 따라 계속 늘려가는데... 정삼각형의 변의 길이가 수열의 값으로 들어간다. 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16... 가장 핵심은 파도반 수열의 규칙을 찾는 것이었습니다. 위의 규칙을 기반으로 하고 있습니다. 근데 조건으로 n이 8보다..
2021. 10. 8.
백준 9095 파이썬 - 1,2,3 더하기 - 동적 계획법, DFS
백준 9095 파이썬 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 알고리즘 문제입니다. 단, 위치의 중복까지 가능한 조건입니다. 예를 들어 4라는 정수를 만들 때 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 이렇게 위치의 중복까지 가능한 조건 입니다. 이 문제는 동적 계획법을 공부하기 위해 풀은 문제인데요... 문제를 해결하는 방법을 고민해 보면서 DFS를 사용하고 싶다는 생각이 많이 들었어요. 순열이나 조합을 구할 때 DFS를 사용해서 ..
2021. 10. 7.
