[Jungol] 정올 1692 곱셈

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=965&sca=20

Approach

① 두번째 3자리 자연수를 나머지 연산을 통해서 각 자리수를 구한 후,

    A와 곱해서 (3), (4), (5) 결과를 쉽게 구할 수 있습니다.

② (6) = (3) × 1 + (4) × 10 + (5) × 100이므로 규칙 이용

---

#include <stdio.h>
 
int N, M, ans;
int use[20];
inline int min(int A, int B) { return A < B ? A : B; }
inline int abs(int x) { return x < 0 ? -x : x; }
 
void DFS(int first, int second, int depth, int moveCnt) {
    // 분기한정
    if (moveCnt > ans) return;
 
    if (depth == M) {
        ans = (ans, moveCnt);
        return;
    }
    DFS(use[depth], second, depth + 1, moveCnt + abs(first - use[depth]));
    DFS(first, use[depth], depth + 1, moveCnt + abs(second - use[depth]));
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    int first, second;
    scanf("%d", &N); // 벽장의 개수
    scanf("%d %d", &first, &second); // 열린 문
    scanf("%d", &M); // 사용 순서
    for (int i = 0; i < M; i++) {
        scanf("%d", &use[i]);
    }
 
    ans = N * M + 1;
    DFS(first, second, 0, 0);
    printf("%d", ans);
}