메밀이네

동적 계획법 단계의 문제를 열심히 풀고 있습니다. 계단 수란 다음 자릿수가 1의 차이를 가지고 이어지는 수입니다 예를들면 3456, 210 등이 있겠습니다. 다이나믹 프로그래밍으로 풀었습니다. 자릿수 N으로 4가 주어졌을 경우 첫번째 숫자의 다음 자리 수는 첫번째 숫자에서 1을 더하거나, 1을 뺀 수가 와야 합니다. 첫번째 숫자가 3일 경우, 다음 자리에 올 수 있는 계단 수는 2와 4인것입니다. 메모제이션 된 2와 4의 값을 더하면 쉽게 현재의 계단 수 개수를 구할 수 있습니다. 0과 9의 경우 다음 자리에 올수있는 숫자가 1과 8로 한정적입니다. 이 경우만 케이스를 분류해서 따로 계산합니다. 1234567891011121314151617181920212223242526272829303132333435..

꽤나 오랫동안 헤메였는데 선행 노드에 대해 이해하고 쉽게 풀 수 있었습니다. DFS에서 방문한 노드를 체크해 큐에서 순서대로 노드를 탐방한다면 위상 정렬은 다음 노드의 선행자가 없을경우만 큐에 푸쉬합니다. 선행자에 대해 확실히 짚고 넘어갔다면 금방 풀었을 것 같습니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #include int* buildingTime;int** buildings;int* pre; int max(int a, int b) { return a > b ? a : b;} i..