Problem Slove

Algorithm Training

[natokim]

1026번: 보물

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0]*B[0] + ... + A[N-1]*B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

풀이

  우선 문제를 봤을 때 B에 있는 수는 재배열 하면 안된다길래 최대한 B배열을 건드리지 않고 문제를 해결 하려고 했다. 기본적인 아이디어는 A의 최소와 B의 최대를 곱하고 A의 최대와 B의 최소를 곱하는 것이다 이렇게 하는 이유는 AB의 수가 음이 아닌 정수라는 점과 큰 수 끼리 곱할 경우 큰 수와 작은수를 곱할 때 보다 더 큰 수가 계산되기 때문이다. 처음에는 A배열만 정렬해서 해결하려 했지만 너무 복잡해지므로 좀 더 생각을 해봤더니 B에 있는 수는 실제로 정렬을 하더라도 아무상관이 없다는 것을 깨달았다. 그래서 A배열을 오름차순 정렬하고 B배열을 내림차순 정렬을 해서 각 n번째 원소들끼리 곱한 후 모두 더하면 최솟값이 된다.

#include #include using namespace std; bool oper (int a, int b){ return a>b; } int n, i, A[1000], B[1000],sum; int main(){ scanf("%d", &n); for (i = 0; i < n; i++){ scanf("%d", &A[i]); } for (i = 0; i < n; i++){ scanf("%d", &B[i]); } std::sort(A,A+n); std::sort(B,B+n,oper); for (i = 0; i < n; i++){ sum+=A[i]*B[i]; } printf("%d", sum); return 0; }

[natokim]

2457번 : 공주님의 정원

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.

정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.

N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오.

풀이

  우선 문제를 풀기 전에 std라는 것에 대해 알게 되었고 std::sort의 사용법을 알아보았다. std::sort는 몇 줄 만에 O(nlog(n)) 시간 복잡도의 정렬 알고리즘을 구현 할 수 있게 도와준다. 몹시 편리하다. 

  공주님의 정원은 처음 문제를 보면 모든 경우의 수를 다 구한 뒤 최적의 답을 골라야 할 것 같지만 사실은 선택했을 때 무조건 이득이 되는 꽃이 존재한다. 그러므로 우선 꽃이 피는 시기로 오름차순 정렬을 한 뒤 3월 1일 보다 빨리 피는 꽃들 중 가장 늦게 지는 꽃을 기준으로 다시 빨리 피는 꽃들을 구하며 이 과정을 반복한 뒤 11월 30일이후에 꽃이 지게 되면 꽃의 개수를 출력한다. 만약 12월 이전에 꽃이 모두 지게 되면 0을 출력한다.

#include #include using namespace std; struct aa{ int sm,sd,em,ed; }map[100005],Max; bool opfs(aa a, aa b) { if (a.sm == b.sm) { if (a.sd == b.sd) { if (a.em == b.em) { return a.ed > b.ed; } return a.em > b.em; } return a.sd < b.sd; } return a.sm < b.sm; } bool opsd(aa a, aa b) { if (a.em == b.em) { return a.ed < b.ed; } return a.em < b.em; } int n,i,nm,nd,ch,cnt,j,e; int main() { scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d%d%d", &map[i].sm, &map[i].sd, &map[i].em, &map[i].ed); } nm = 3; nd = 1; std::sort(map,map+n,opfs); e = 0; while(1) { ch = nm*100+nd; /* for (i = 0; i < n; i++) { printf("%d %d %d %d\n",map[i].sm,map[i].sd,map[i].em,map[i].ed); } printf("\n"); */ for (i = e; i < n; i++) { if (map[i].sm < nm || (map[i].sm == nm && map[i].sd <= nd)) { if (Max.em < map[i].em || (Max.em == map[i].em && Max.ed <= nd)) { Max.em = map[i].em; Max.ed = map[i].ed; } } else { break; } } /* for (j = 0; j < n; j++) { printf("%d %d %d %d\n",map[j].sm,map[j].sd,map[j].em,map[j].ed); } printf("\n"); */ nm = Max.em; nd = Max.ed; e = i; cnt++; // printf("%d %d %d\n\n", nm, nd, e); if (nm*100+nd <= ch) { printf("0"); break; } if ((nm == 11 && nd == 30) || nm == 12) { printf("%d", cnt); break; } } return 0; }

[natokim]

2163번: 초콜릿자르기

정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다.

초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 같이 초콜릿을 쪼개면 초콜릿은 두 개의 조각으로 나눠지게 된다. 이제 다시 이 중에서 초콜릿 조각을 하나 들고, 쪼개는 과정을 반복하면 된다.

초콜릿을 쪼개다 보면 초콜릿이 녹을 수 있기 때문에, 정화는 가급적이면 초콜릿을 쪼개는 회수를 최소로 하려 한다. 초콜릿의 크기가 주어졌을 때, 이를 1×1 크기의 초콜릿으로 쪼개기 위한 최소 쪼개기 회수를 구하는 프로그램을 작성하시오.

풀이

  처음에 이 문제를 봤을 때 어떻게 접근을 해야 할지 감이 잘 오지 않았다. 그래서 그림을 그려보니 초콜릿은 NxM크기의 직사각형 형태이므로 어떤 방식으로 자르더라도 같은 결과가 나오게 된다.

  가로로 계속 자른 뒤 세로로 자르는 경우 가로로 N-1번 만큼 자른 뒤 Nx(M-1)번만큼 잘라야 한다. 이것을 수식화 하면 N-1+Nx(M-1)이므로 이를 단순화 시키면 N*M-1이라는 결론을 도출할 수 있다.

  세로로 계속 자른 뒤 가로로 자르는 경우 가로로 M-1번 만큼 자른 뒤 Mx(N-1)번만큼 잘라야 한다. 이것을 수식화 하면 M-1+Mx(N-1)이므로 이를 단순화 시키면 N*M-1이라는 결론을 도출할 수 있다.

  위 두 가지 경우를 토대로 N*M-1이라는 공식이 성립함을 알 수 있다. 처음에 내가 너무 어렵게 생각한 것 같다.

#include int n,m; int main(){ scanf("%d%d",&n,&m); printf("%d",n*m-1); return 0; }

[natokim]

시간복잡도 개념

처리해야 하는 데이터들에 따라 걸리는비례적인 시간을 나타낸다 O()와 같이 표기

O(1)

데이터의 크기에 상관없이 일정 시간 안에 실행을 마침.(상수시간라고도 부름)

O(n)

데이터의 크기에 비례하는 시간이 걸림

선형시간이라고도 부름

순차검색이 해당됨.

O(n²)

n²에 비례하는 시간이 걸림

선택정렬이 해당됨

O(log n)

이진검색이 해당됨

O(nlogn)

힙정렬이 해당됨

[natokim]

2953번: 나는 요리사다

"나는 요리사다"는 다섯 참가자들이 서로의 요리 실력을 뽐내는 티비 프로이다. 각 참가자는 자신있는 음식을 하나씩 만들어오고, 서로 다른 사람의 음식을 점수로 평가해준다. 점수는 1점부터 5점까지 있다.

각 참가자가 얻은 점수는 다른 사람이 평가해 준 점수의 합이다. 이 쇼의 우승자는 가장 많은 점수를 얻은 사람이 된다.

각 참가자가 얻은 평가 점수가 주어졌을 때, 우승자와 그의 점수를 구하는 프로그램을 작성하시오.

풀이

이 문제는 정렬을 오름차순으로 하는 것이 가장 큰 난관이었다. 맨 처음에 생각한 방법은 각각의 요소들 마다 배열 전체를 탐색하며 위치를 결정하는 것이었다. 하지만 이 방법은 시간과 공간적으로 너무 비효율적이었다. 그래서 정렬 알고리즘을 검색 해보니 여러 알고리즘이 나왔지만 그 중에 비교적 구현하기 간단한 선택정렬을 이용해서 구현해보았다.

#include int i,j,a,map[10],w[10],temp; int main(){ for (i = 0; i < 5; i++){ for (j = 0; j < 4; j++){ scanf("%d",&a); map[i]+=a; } w[i] = i; } for (i = 0; i < 4; i++){ for (j = i; j < 5; j++){ if (map[i] < map[j]){ temp = map[i]; map[i] = map[j]; map[j] = temp; temp = w[i]; w[i] = w[j]; w[j] = temp; } } } printf("%d %d", w[0]+1, map[0]); return 0; }

[natokim]

1009번: 분산처리

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번 까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

우선 ab 는 직접 계산하기에 너무 크다. 그러므로   ab직접 계산하는 것은 무리이므로 다른 아이디어를 생각해봐야 했다.

그래서 생각 해낸 아이디어가 재용이의 컴퓨터가 10대인 것을 이용하는 것이다. ab  번째 데이터는 결국에 10대 컴퓨터에서 순서대로 처리하게 되므로 일의 자리 만을 계속 거듭 제곱 하게 되면 연산이 끝난 후의 일의 자리 숫자가   ab  번째 데이터를 처리하게 될 컴퓨터 번호가 된다.

여기서 예외가 존재하는데 ab 데이터가 일의 자리 숫자가 0이라면 10번째 컴퓨터를 이용하게 된다.

#include int main() { int a,b,n,i,j,temp; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d%d", &a, &b); temp = a; for (j = 0; j < b-1; j++) { a=temp*a%10; } if (a == 0) { printf("10\n"); continue; } printf("%d\n", a); } return 0; }

[natokim]

2743 단어길이재기 풀이

알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오.

#include #include int main() { char a[105]; scanf("%s", a); printf("%d",strlen(a)); return 0; }

[natokim]

1000번: A+B 풀이

A와 B를 입력 받고 두 수를 더해서 출력

#include int main() { int a,b; scanf("%d%d", &a,&b); printf("%d", a+b); return 0; }