이녀기의 자유 탐구

noj.am/1562 백준 1562번 계단 수 문제이다. 문제) '계단 수'는 인접한 숫자간의 차가 모두 1인 수를 가리킨다. 자연수 N이 주어졌을 때, N자리 계단 수 중 0~9 모든 숫자가 등장하는 계단 수의 개수를 출력하세요. 풀이) 처음엔 N 이하인 모든 계단수의 개수를 계산하는 줄 알고 백트래킹을 생각했다. 그런데 문제를 다시 읽어보니 0~9 모든 숫자가 들어가야한다는 조건이 있어서 함수 인자로 used라는 set을 추가했다. 그럼에도 TLE(시간초과)가 나서 백트래킹으로 풀기 적합하지 않은 문제란 생각이 들었다. 백트래킹으로 계산하면 0~9가 모두 들어가지 못하는 케이스를 불필요하게 많이 체크하기 때문에 비효율이 발생한다. 문제에서 집중할 부분은 크게 3가지이다. "지금까지 결정한 자리(dig..

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 그려보면서 일반화했는데, 틀렸다고 나와서 예외를 찾느라 시간을 소모했다. integer 범위를 넘어가서 문제가 생긴걸 확인하곤 고쳐서 금방 풀었다. 문제) 나선 모양으로 놓인 삼각형의 변의 길이를 구하여라. 놓인 삼각형 중 가장 긴 변에 그 변의 길이를 한 변의 길이로 하는 삼각형을 놓는다. (1

www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 오랜만에 PS를 했다. DP 문제로 하나 풀려했는데, 정답률에 맞게 난이도가 쉬웠다. 문제) 0번째, 1번째 피보나치 수를 0, 1로 정의한다. 20 이하의 자연수 n을 입력했을 때, n번째 피보나치 수를 출력하시오. 풀이) 간단한 dp문제. 1차원 배열로 DP 테이블을 정의하고, 메모이제이션을 이용한 다음 입력받은 n을 인덱싱해서 출력하면 된다. C 코드) #includ..