최근에는.. 할 일이 너무 많아서 우선순위에서 밀려나는 바람에 문제를 많이 안풀었다.. 다시 차근차근 코테 준비를 해볼까 한다.. (2022-2 알고리즘 때 구현하기는 했음, 이것도 정리해서 올릴 예정)
다시금 감을 잡기 위해 이코테 책을 앞에서부터 다 풀기로 했다.
큰 수의 법칙
배열의 주어진 수를 M번 더해 가장 큰 수를 만드는 문제로 이때 특정 인덱스의 수는 연속으로 K번을 초과해 더할 수 없다.
처음 이 문제를 풀 때는 [가장 큰 수를 K번, 그 다음으로 큰 수 1번]을 반복해서 가장 큰 수를 구했다. 하지만 이는 비효율적인 방법이었고 알맞은 수식을 찾아내서 한 번에 해결할 수 있었다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int main() {
int N, M, K;
int num[1000];
int i,j;
int big, big2, sum;
int count;
scanf("%d %d %d", &N, &M, &K);
for (i = 0; i < N; i++) {
scanf("%d", &num[i]);
}
sort(num, num+N, greater<int>());
big = num[0];
big2 = num[1];
count = (M / (K + 1)) * K + M % (K + 1);
sum = count * big + (M - count) * big2;
/* //수식을 사용하지 않고 하나씩 돌려보면서 푼 것
sum = 0;
j = 0;
for (i = 0; i < M; i++) {
if (j / K == 0) {
sum += big;
j++;
}
else {
sum += big2;
j = 0;
}
}
*/
printf("%d", sum);
}
/*
5 8 3
2 4 5 4 6
*/
숫자 카드 게임
숫자 카드 중에서 같은 행에서는 가장 작은 카드를 뽑고 뽑힌 카드 중 가장 높은 숫자가 쓰인 카드를 뽑는 문제였다.
굉장히 간단한 문제였는데
- 한 행에서 가장 작은 카드를 뽑는다. (rowMin)
- 1에서 뽑은 카드와 뽑힌 카드의 최댓값을 비교해 업데이트 해준다 (min) (변수를 max로 지정할걸 그랬다)
풀 때 맨 앞의 값으로 min 값들을 초기화 해줬는데, 문제에서 카드 숫자의 범위가 1~10000 이라고 지정해 준 것을 나중에 발견했다. 아래처럼 초기화할 필요 없이 항상 맨 처음에 10001이라고 지정해 주는 것이 더 편할 것 같다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int main() {
int N, M;
int min, rowMin;
int num[101][101];
int i, j;
scanf("%d %d", &N, &M);
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
scanf("%d", &num[i][j]);
if (j == 0) { //rowMin 초기화
rowMin = num[i][j];
}
if (rowMin > num[i][j]) {
rowMin = num[i][j];
}
}
if (i == 0) { //min 초기화
min = rowMin;
}
//printf("min: %d rowMin: %d\n", min, rowMin);
if (min < rowMin)
min = rowMin;
}
printf("%d", min);
}
/*
3 3
3 1 2
4 1 4
2 2 2
2 4
7 3 1 8
3 3 3 4
*/
1이 될 때까지
N-1을 하거나 N/K (N이 K로 나누어 떨어질 경우에만 가능) 을 해서 N을 1로 만드는 문제였다.
처음에 잘못 생각해서 K를 계속 곱한 후 남은 숫자를 더해주는 방법을 생각했는데, 이 경우는 거듭제곱에만 사용할 수 있어서 답이 다르게 나왔다.
5*5 = 25 -> 2번 필요 4*4 + 1 = 17 -> 3번 필요
책의 문제에서 나온 경우의 출력 예시와 동일해서 틀린지도 모르고 있다가 설명 부분의 예시인 25,3인 경우에서 발견할 수 있었다. 내가 푼 방식대로라면 3*3 + 16 -> 17 이어야 하는데 책의 정답은 6이었다..
다시 풀었는데 처음보다 더 쉽게 생각하면 금방 답이 나오는 문제였다;
N이 K로 나눠질 때까지 -1을 하다가 N을 K로 나누는 것을 반복하면 된다!
이때 시간을 더 줄이기 위해 N%K를 빼주는 방법을 사용했다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
int main() {
int N, K;
int i = 0;
int x;
scanf("%d %d", &N, &K);
while (N > 1) {
if (N % K == 0) {
N /= K;
i++;
}
else {
x = N % K;
N -= x;
i += x;
}
//printf("N: %d\n", N);
if (N == 0) i -= 1;
}
printf("%d", i);
}
/*
25 5
*/