sfpc 준비하기
총평
문제는 무난했다.
실수나 긴장만 하지 않는다면 sfpc문제들을 대부분 풀 수 있을것 같다.
준비하기 문항
주차 공간1
어떤 주차장에 n개의 주차 공간이 있고, 각 주차 공간의 바닥에는 1부터 n까지의 번호가 쓰여있다.
다음은 주차 공간이 22개인 주차장의 모습이다.
다음 그림은 첫째 날 9시의 주차 공간 상태이다.
다음 그림은 둘째 날 9시의 주차 공간 상태이다.
주차 공간이 n개인 주차장에 대하여 이틀간의 주차 상태를 입력 받아, 이틀 동안 모두 사용되지 않은 주차 공간의 개수와 이틀 동안 모두 사용된 주차 공간의 개수를 출력해보자.
풀이 (implementation)
bool 배열을 사용해서 주차가 되었는지 판별하였다.
단순한 구현문제.
#include <iostream>
using namespace std;
int main(){
bool map[101]={0};
int n,a,b,x,cntx=0,cnto=0;
cin >> n >> a >> b;
while(a--){
cin >> x;
map[x]=true;
}while (b--){
cin >> x;
if(map[x])cnto++;
map[x]=true;
}for(int i=1; i<=n; i++){
if(!map[i])cntx++;
}cout << cntx << ' ' << cnto;
}
한라봉 포장1
알바왕 비버가 한라봉 상자 포장 아르바이트를 한다.
상자의 크기는 용량에 따라 4종류(1kg, 3kg, 5kg, 10kg)로 나뉘는데, 반드시 상자의 용량만큼 한라봉을 담아야 한다.
즉, 상자의 용량보다 부족하거나 초과하여 한라봉을 담을 수 없다.
또한, 상자를 최소한으로 사용해서 한라봉을 포장해야 한다.
예를 들어, 3kg의 한라봉을 포장하기 위해서는 1kg 상자 3개가 아닌, 3kg 상자 1개를 사용해야 한다.
비버가 n kg의 한라봉을 모두 포장하려면, 최소 몇 개의 상자가 필요할까?
풀이 (greedy)
단순한 그리디 문제다.
#include <iostream>
using namespace std;
int main(){
int n,cnt=0;
cin >> n;
while(n>=10){
n-=10;
cnt++;
}while(n>=5){
n-=5;
cnt++;
}while(n>=3){
n-=3;
cnt++;
}while(n>=1){
n-=1;
cnt++;
}cout << cnt;
}
약수 배수 놀이1
백록담에서 돌하르방과 n마리의 제주 흑돼지들이 약수 배수 놀이를 하고 있다.
돌하르방이 고른 자연수가 m이고, n마리의 흑돼지가 고른 자연수가 각각 v1, v2, … , vn 일 때,
돌하르방이 답해야하는 수를 출력해보자.
풀이 (dp, eratosthenes_sieve)
이거 시간제한이 너뿌 빡빡했다.
대부분의 일반적인 학생들? 시간제한 때문에 절대 못푼다.
에라토스테네스의 체를 활용하여 10000000이하의 각각의 수에 소수를 구해준다.
그리고 에라토스테네스의 체를 응용하여 10000000이하의 각각의 수에 약수를 구해주면 끝이다.
배수는 그냥 나누면 된다.
산딸기 정렬1
비버는 산딸기를 딴 후, 특별한 방법으로 정렬하고 다양한 레시피로 조리하여 먹는다.
비버가 산딸기를 정렬하고 조리하는 규칙은 다음과 같다.
- 특정 크기(n)의 산딸기는 생으로 먹는다.
- 특정 크기(n)보다 큰 산딸기는 파이로, 특정 크기(n)보다 작은 산딸기는 쥬스로 만들어 먹는다.
- 산딸기는 크기에 따라 쥬스, 생 산딸기, 파이용 순으로 정렬한다.
- 같은 용도의 산딸기는 딴 순서대로 정렬한다.
산딸기의 개수(m), 각 산딸기의 크기(a1, a2, … , am), 특정 크기(n)이 주어질 때, 산딸기를 정렬한 결과를 출력해보자.
풀이 (sort, implementation)
일단 산딸기를 용도 별로 3개의 for문을 만들어 준다.
그려면 같은 용도의 산딸기는 딴 순서대로 정렬하기 때문에
조건에 맞는 것을 출력하면 된다.
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n,m;
vector<int> a,b;
cin >> n;
for(int i=0; i<n; i++){
cin >> m;
a.push_back(m);
}cin >> m;
for(int i=0; i<n; i++){
if(a[i]<m)cout << a[i] << ' ';
}for(int i=0; i<n; i++){
if(a[i]==m)cout << a[i] << ' ';
}for(int i=0; i<n; i++){
if(a[i]>m)cout << a[i] << ' ';
}
}
감귤 나무 관리1
감귤왕 비버는 원형 감귤밭의 감귤 나무를 3종류로 구분하여 관리한다.
비버는 밭의 중심 좌표, 밭의 반지름, 각 감귤 나무의 좌표 데이터를 활용해서
밭 내부에 위치한 나무(in), 밭 경계에 위치한 나무(on), 밭 외부에 위치한 나무(out)로 구분한다.
감귤밭의 중심 좌표가 (a, b)이고 감귤밭의 반지름이 r, 좌표 (c, d)에 위치한 감귤 나무는 어떻게 구분될까?
풀이 (geometry)
a-c와 b-d의 절댓값을 구하고 피타고라스의 정리를 사용하여 구하였다.
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int a,b,r,c,d,x,y;
cin >> a >> b >> r >> c >> d;
x=abs(a-c);y=abs(b-d);
if(sqrt(x*x+y*y)>r)cout << "out";
else if(sqrt(x*x+y*y)==r)cout << "on";
else cout << "in";
}
도전하기 문항
자녀의 혈액형1
ABO 혈액형 분류식을 기준으로, 부모의 혈액형 인자 정보를 알고 있을 때 나올 수 있는 자녀의 혈액형을 판단하는 기준은 다음과 같다.
부모의 혈액형 인자 정보를 입력받았을 때, 나올 수 있는 자녀의 혈액형을 모두 출력해보자.
풀이 (implementation)
흔히 말하는 빡구현 문제.
#include <iostream>
using namespace std;
int main(){
string a,b;
cin >> a >> b;
if(a=="AB"||b=="AB"){
if((a=="AO"||b=="AO")||(a=="BO"||b=="BO")||(a==b))cout<<"A AB B";
else if(a=="AA"||b=="AA")cout<<"A AB";
else if(a=="BB"||b=="BB")cout<<"AB B";
else cout<<"A B";
}else if(a[0]=='A'&&b[0]=='A'){
if(a[1]=='O'&&b[1]=='O')cout<<"A O";
else cout<<"A";
}else if(a[0]=='B'&&b[0]=='B'){
if(a[1]=='O'&&b[1]=='O')cout<<"B O";
else cout<<"B";
}else if(a=="OO"||b=="OO"){
if(a=="AB"||b=="AB")cout<<"AB O";
else if(a[1]=='A'||b[1]=='A')cout<<"A";
else if(a=="AO"||b=="AO")cout<<"A O";
else if(a[1]=='B'||b[1]=='B')cout<<"B";
else if(a=="BO"||b=="BO")cout<<"B O";
else cout<<"O";
}
else if(a[0]=='A'||b[0]=='A'&&a[0]=='B'||b[0]=='B'){
if(a[1]=='O'||b[1]=='O'){
if(a[1]==b[1])cout<<"A AB B O";
else if((a[1]=='O'||b[1]=='O')&&(a[1]=='A'||b[1]=='A'))cout<<"A AB";
else cout<<"AB B";
}else cout<<"AB";
}
}
해녀 비버1
제주 앞바다에서 보말(‘바다 고둥’의 제주 방언)을 채취한 해녀 비버가 장터에서 다른 해산물과 교환하려 한다. 장터에서는 아래 기준으로 해산물을 교환할 수 있다.
해녀 비버가 n마리의 보말을 채취하였을 때, 교환 가능한 다금바리가 최대 몇 마리인지 출력해보자.
풀이 (greedy)
쉬운 그리디 문제
#include <iostream>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
unsigned long long n,m=0,a,b,c;
cin >> n >> a >> b >> c;
m=n/12;
n=m*a;
m=n/8;
n=m*b;
m=n/5;
n=m*c;
cout<<n;
}
덧셈왕 비버1
덧셈왕 비버에게는 연속 부분 수열을 계산하는 2가지 특별한 능력이 있다. 이때, 연속 부분 수열이란 차례대로 나열한 1개 이상의 수의 묶음이다.
덧셈왕 비버의 능력은 다음과 같다.
- 연속 부분 수열의 합을 2초 안에 계산할 수 있다.
- 연속 부분 수열의 개수를 2초 안에 구할 수 있다.
예를 들어, 다음과 같이 10개의 수를 나열한 수열이 있을 때,
덧셈왕 비버는 3번째 수부터 7번째 수까지의 연속 부분 수열의 합(27)을 2초 안에 계산할 수 있다.
또한, 앞서 구한 27과 합이 같은 연속 부분 수열의 개수(4개)를 2초 안에 구할 수 있다.
n개의 수를 나열한 수열이 입력되었을 때, a번째 수부터 b번째 수까지의 합을 구한 후, 그 합과 같은 연속 부분 수열의 개수를 출력해보자.
풀이 (implementation)
이중 for문으로 풀었다.
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n,m,a,b,sum=0,su,cnt=0;
vector<int> v;
cin >> n;
for(int i=0; i<n; i++){
cin >> m;
v.push_back(m);
}cin >> a >> b;
for(int i=a-1; i<b; i++){
sum+=v[i];
}for(int i=0; i<n; i++){
su=0;
for(int j=i; j<n; j++){
if(su>=sum)break;
su+=v[j];
}if(su==sum)cnt++;
}cout << cnt;
}
덧셈왕 비버2
덧셈왕 비버1과 차이점은 입력되는 수가 늘어났고, 음수까지 추가되었다.
첫 번째 줄에 수의 개수(n)가 입력된다.
두 번째 줄에 n개의 수(ci, c1, … , cn)가 스페이스로 구분되어 입력된다.
세 번째 줄에 a, b가 스페이스로 구분되어 입력된다.
[1<=n<=3000]
[-100000<=ci<=100000]
[1<=a<=b<=n]
풀이 (prefix_sum)
누적합 알고리즘을 사용하였다.
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n,m,a,b,sum=0,su,cnt=0,s[3001]={0};
vector<int> v;
cin >> n;
for(int i=0; i<n; i++){
cin >> m;
v.push_back(m);
}cin >> a >> b;
for(int i=1; i<n+1; i++){
s[i]=s[i-1]+v[i-1];
}
for(int i=a-1; i<b; i++){
sum+=v[i];
}for(int i=0; i<n; i++){
for(int j=i+1; j<n+1; j++){
if(s[j]-s[i]==sum)cnt++;
}
}cout << cnt;
}
칭찬 스티커1
비버고등학교에서는 아래 규칙에 따라 칭찬 스티커를 발급한다.
- 칭찬 스티커는 평일, 주말에 관계없이 매일 발급한다.
- 각 학생은 1년에 1개의 스티커만 받을 수 있으며, 한 번 스티커를 받으면 다시는 받지 못한다.
- 3월 1일에 학생 중 한 명을 선정하여 칭찬 스티커를 발급한다.
- 칭찬 스티커를 받은 학생은 다음 날 새로운 학생들에게 칭찬 스티커를 발급하는데, 발급하는 날의 날짜가 소수인지 아닌지에 따라 다음과 같이 발급하는 스티커의 개수가 달라진다.
- 날짜가 소수가 아닌 경우 : 전날 스티커를 발급받은 학생이 2명의 학생에게 스티커를 발급
- 날짜가 소수인 경우 : 전날 스티커를 발급받은 학생이 3명의 학생에게 스티커를 발급
비버고등학교의 학생이 n명이라고 할 때, 모든 학생이 칭찬 스티커를 받기 위해서 최소 몇 일이 필요할까?
칭찬 스티커 제도는 3월 1일에 처음 시작된다.
풀이 (implementation)
달 배열을 먼저 만들어두는게 도움이 된다.
#include <iostream>
using namespace std;
bool isPrime(int n){
if (n <= 1)
return false;
if (n <= 3)
return true;
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
int main(){
unsigned long long n,cntm=2,m=1,i=2,t=1,check=1;
int month[12]={31,28,31,30,31,30,31,31,30,31,30,31};
cin >> n;
while(m<n){
if(month[cntm]<i){
i=1;
cntm=(cntm+1)%12;
}
if(isPrime(i))t*=3;
else t*=2;
m+=t;
i++;
check++;
}cout << check;
}
한라산 등반1
오름 등반 동호회 회원인 동백, 철쭉, 유채는 주기적으로 한라산을 등반한다.
세 회원의 한라산 등반 주기는 다음과 같다.
- 동백 : a일마다 한라산 등반
- 철쭉 : b일마다 한라산 등반
- 유채 : c일마다 한라산 등반
2100년 1월 1일 금요일에 처음으로 셋이 함께 한라산을 등반한 후 각자의 등반 주기에 맞춰 등반할 때, 동백, 철쭉, 유채가 함께 한라산을 오르는 다음 등반 날짜와 요일은 언제일까? 주의! 2100년부터는 지구 환경이 변하여, 12월이 사라지고 1월부터 11월까지만 있다. 그러나 윤년 규칙은 변하지 않았다.
풀이 (implementation)
2100년 1월 1일이 무슨 요일인지 알아야 풀기 쉬워진다.
#include <iostream>
using namespace std;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int lcm(int a, int b) {
return a * (b / gcd(a, b));
}
int main(){
int month[12]={31,28,31,30,31,30,31,31,30,31,30};
int a,b,c,n,dx=0,m=0,y=2100,d=1;
char days[7][4]={"FRI","SAT","SUN","MON","TUE","WED","THU"};
scanf("%d%d%d",&a,&b,&c);
n=lcm(c,lcm(a,b));
for(int i=0; i<n; i++){
dx++;
dx%=7;
if(y%4==0&&y%100!=0||y%400==0)month[1]=29;
else month[1]=28;
if(month[m]==d){
if(m==10){
m=0;
y++;
}else m++;
d=0;
}d++;
}printf("%04d-%02d-%02d %s",y,m+1,d,days[dx]);
}