백준 1740 거듭제곱
www.acmicpc.net/problem/1740 1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를 �� www.acmicpc.net 이 문제는 solved.ac기준 브론즈 1로 매겨져 있지만, 얼핏 보면 상당히 어려울 수도 있다. 아니 솔직히 아직도 이게 왜 브론즈 1인지 조금 의문이다. 필자도 처음에는 이걸 어떻게 풀지?라는 어려움이 있었다. 알고 보면 간단하고 코드도 짧다. 하지만 모르면 어렵다. 위의 그림에서 보듯이 문제에서 N이 주어졌을 때, 그 N을 이진수로 표현하면 1001001 등으로 표현된..
백준 9095 - 1, 2, 3 더하기
www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이전 포스팅과 마찬가지로 이번에도 다이나믹 프로그래밍 문제이다. 아주 기본적인 형태이다. DP(Dynamic Programming)문제를 풀 때, 가장 중요한 것 중 하나가 바로 점화식을 구하는 것이다. 점화식이란 말 그대로 어떠한 연속된 연산의 불을 붙여주는 기초 공식이라고 볼 수 있다. 즉, 이전 포스팅(백준 회의실 배정 문제)에서 살짝 언급한 바와 같이, 연속된 연산이 하나의 공식(점화식)하에서 계속 이루어지기 위해서는 모든 정점(상황)에서 항상 같은 규칙이 적용될 수 있어야 한다. 이 문제에서는 어떠한..
