백준 - 장신구 명장 임스(25496번)

백준 - 장신구 명장 임스(25496번)

문제

• 메이플스토리에는 전문 기술이라는 제작 시스템이 있다. 전문 기술은 특정량의 피로도가 쌓이는 대신 다양한 장비 및 비약을 제작할 수 있는 시스템이다. 장신구 명장인 임스는 어떻게 하면 더 효율적으로 많은 장신구를 제작할 수 있을지 고민에 빠졌다.

• 임스가 만들 수 있는 장신구는 $N$개가 있고, 각각의 장신구를 만들면 $A_i$만큼의 피로도가 누적된다.

• 피로도가 $200$ 미만인 경우, 장신구를 제작할 수 있다. 현재 쌓인 피로도가 $P$일 때, 임스가 제작할 수 있는 장신구의 최대 개수를 구해보자!

입력

• 첫 번째 줄에 정수 $P$와 정수
  $N$이 공백으로 구분되어 주어진다.
  ($1 \le P \le 200$, $1 \le N \le 1\,000$)

• 두 번째 줄에는 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 200$)

출력

제작할 수 있는 장신구의 최대 개수를 출력하시오.

이 문제는 배열 A를 오름차순 정렬하는 것이 포인트이다.

---

코드 설계

문제 해결의 단계는 아래와 같다.

1. 피로도를 변수 P로, 장신구의 갯수를 변수 N으로 입력받는다.
2. 각각의 장신구의 피로도를 배열 A로 입력받는다.
3. 배열 A를 오름차순 정렬한다.
4. P가 200 미만이면서 장신구의 갯수만큼 반복한다.
5. 반복한 횟수를 index에 저장하여 출력한다.

---

제출한 답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int asc(const int* a, const int* b) {
	return *a - *b; // 오름차순
}

int main() {
	int P, N;
	scanf("%d %d", &P, &N);

	int A[1000];
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}

	qsort(A, N, sizeof(int), asc);

	int index = 0;

	while (P<200 && index<N) {
		P += A[index++];
	}

	printf("%d", index);
}

---

시행착오

• C에서 오름차순, 내림차순 함수를 사용하는 것은 백준 - 보물(1026번) 글에서 사용 및 설명한 적이 있다.

오답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int asc(const int* a, const int* b) {
	return *a - *b; // 오름차순
}

int main() {
	int P, N;
	scanf("%d %d", &P, &N);

	int A[1000];
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}

	qsort(A, N, sizeof(int), asc);

	int index = 0;

	while (P<200) { // while (P<200 && index<N)
		P += A[index++];
	}

	printf("%d", index);
}

처음 시도에서는 index의 값이 장신구의 갯수인 N회를 넘어가는 것을 고려하지 못하여 틀렸었다. 이러한 반례를 찾아 수정하였다.

---

💡한줄평

JS와 권태기인지 자꾸 하기 싫어져서 문제풀이를 스터디 당일까지 최대한 미루다가 푸는 중이다. 그래서 이제는 언어에 제한을 두거나 부담을 가지지 않고 우선 문제 풀이 자체에 친숙해지는 연습을 먼저 하려고 한다. 차차 연습하고 노력하다보면 분명히 성장하는 날이 올 것이다!