[4일차] 수막대

- 문제 설명

수 막대를 이용해서 길이를 주어진 길이를 만족하라

5, 2, 3으로 6을 만들기 위해선

5에서 2를 뺀뒤 3을 더해야한다.

이런식으로 빼고 더할 수 있음

- 입력

1 // 테스트 케이스

8 3 // 목표 길이, 수막대 갯수

2 6 7 // 각각 수막대의 길이

- 출력

#1 2 // 테스트케이스, 2개

- 입력 예시

3
8 3
2 6 7
10 4
3 4 5 6
12 5
4 2 3 7 8

- 출력 예시

#1 2
#2 2
#3 2

- 코드

#include "stdio.h"

int findMinNumOfStrck(int startLength);

int L, N;

int queue[101];

int front;

int rear;

int stickNum[101];

int stick[5]; // 막대 종류

int main(int argc, const char * argv[]) {

    int T;

    scanf("%d", &T);

    for(int tc = 1;tc <= T;tc++)

    {

        front = -1;

        rear = -1;

        

        scanf("%d %d",&L, &N);

        for(int i =0;i<N;i++)

        {

            scanf("%d",&stick[i]);

        }

        

        printf("#%d %d\n",tc,findMinNumOfStrck(0));

        for(int i=0;i<= L;i++) // 스틱 갯수 초기화

        {

            stickNum[i] = 0;

        }

    }

    return 0;

}

int findMinNumOfStrck(int startLength)

{

    queue[++rear] = startLength; // 시작 길이 0

    stickNum[startLength] = 1; // 처음 갯수는 1로 초기화

    

    while (front != rear) // 큐에 아직 남아있는 경우

    {

        int length = queue[++front]; // 큐에서 값을 꺼냄

        if (length == L) // 목표 길이를 만족한 경우

            return stickNum[length] - 1; // 현재 스틱갯수에서 1을 뺌(길이가 0일때 1개부터 시작했기 때문)

        for(int i=0;i < N; i++)

        {

            if((startLength - stick[i]) >= 0 && stickNum[startLength-stick[i]] == 0) // 뺀 값이 0보다 크면 빼서 큐에 넣고

            {

                queue[++rear] = startLength - stick[i];

                stickNum[startLength - stick[i]] = stickNum[startLength] + 1; // 갯수는 하나 늘림

            }

            if((startLength + stick[i]) <= L && stickNum[startLength + stick[i]] == 0) // 더한 값이 L보다 작거나 같으면 더해서 큐에 넣고

            {

                queue[++rear] = startLength + stick[i];

                stickNum[startLength + stick[i]] = stickNum[startLength] + 1; // 갯수는 하나 늘림

            }

        }

    }

    return 0;

}