교재 30p에 나오는 사탕분배 문제, 코드로 구현하신 분 계신가요?

  • dlgusdn616
    dlgusdn616

    저는 사탕분배 문제를 아래와 같은 알고리즘으로 구현했습니다. 하지만, 각 사탕 무게의 편차가 그리 심하지 않다는 가정하에 제대로 작동한다는 제약점이 존재합니다. 한 번 봐주시고 더 좋은 아이디어로 구현하신 분이 있다면 한 수 가르쳐주시면 정말 감사하겠습니다.

    1. 사탕의 개수 N개 만큼의 int형 배열 candy를 동적 생성 // 이는 N개 만큼의 무게를 각 저장하기 위한 배열이다.

    2. 20 이하의 정수 값들을 랜덤으로 candy 배열의 각 인덱스에 차례로 채워 넣는다.

    3. 3명의 어린이가 받은 사탕의 총 무게를 저장할 int child[3] 배열 생성 // 어린이들이 사탕을 받을 때마다 무게가 누적되어 값 갱신

    < 여기서부터 루프 > 사탕의 갯수 N번 만큼 반복
    for(int i = 0; i < N; i++)

    1. 매 실행 별로 최소의 무게를 가지는 child 배열의 index를 기억 // 가장 적은 무게를 가진 아이를 찾아내기 위해 각 실행별 3번의 비교 연산이 발생합니다. 아이의 수가 많다면, 연산의 횟수가 늘어납니다.

    2. 최소 index를 찾았다면, child[index]에 캔디 배분 // candy[index] += candy[i]; 의 형태로 구현

    <루프 종료> // 매 실행별 가장 적은 무게의 캔디를 가진 아이를 찾아내어 우선 배분해주는 방식으로 구현했습니다.

    • 마지막으로 child 배열에서 가장 큰 값과 가장 작은 값을 도출하여 차이를 계산해 출력합니다.

    // 조잡하고 허접하여 고수님들의 도움의 손길 기다리겠습니다.


    3주 전
0개의 댓글이 있습니다.
  • 댓글을 남기시려면 로그인하세요.