개발 블로그

문제 링크 : www.acmicpc.net/problem/16922

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

접근 방법

완전탐색 문제라 모든 경우의 수에 대해 DFS 로 풀었는데 시간 초과가 떴다.

문제의 조건에서 순서를 상관하지 않으므로 IIX = XII 이다. 이는 중복 조합으로 해결할 수 있다.

중복조합은 서로 다른 n개 중 k 개를 뽑는 경우인데, 여기서는 서로 다른 4개(I,V,X,L) 개 중 중복을 허용하고 순서 상관 없이 N개를 뽑는것이다.

DFS() 안의 반복문을 보자.

시작 값을 변화시킴으로써 중복 조합을 구현할 수 있다. i의 변화 값은 다음과 같다. (4개만 나타냄)

(앞에 -가 붙은 경우는 시작 값을 i=0으로 고정시켰을 경우에 나오는 경우이다. 시작 값을 변화시킴으로써 IIX = XII 처럼 같은 수를 나타내는 경우 한번만 카운트 할 수 있다.)

0 0 0 0

0 0 0 1

0 0 0 2

0 0 0 3

- 0 0 1 0

0 0 1 1

0 0 1 2

0 0 1 3

- 0 0 2 0

- 0 0 2 1

0 0 2 2

0 0 2 3

- 0 0 3 0

- 0 0 3 1

- 0 0 3 2

0 0 3 3

...

//
//  BF_BOJ16922_로마숫자만들기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

#define I 1
#define V 5
#define X 10
#define L 50

int N;
int answer = 0;
int sum = 0;
bool visited[1001] = {0};
char cArr[4] = {'I','V','X','L'};
int iArr[4] = {1,5,10,50};

vector<int> sumVec;
vector<string> strVec;
string str = "";
void pickDFS(int toPick, int start, int s){
    
    
    if(toPick==0){
        if(visited[s]==false){
            answer++;
            visited[s]=true;
        }
        return;
    }
    
    for(int i = start; i<4; i++){				//시작점을 바꿔서 중복 조합 구현 가능
        pickDFS(toPick-1, i, s+iArr[i]);
    }
    
}


int main(){
    cin>>N;
    pickDFS(N, 0, 0);
    cout << answer;
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16917

문제

현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 A원, 후라이드 치킨 한 마리의 가격은 B원, 반반 치킨 한 마리의 가격은 C원이다.

상도는 오늘 파티를 위해 양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하려고 한다. 반반 치킨을 두 마리 구입해 양념 치킨 하나와 후라이드 치킨 하나를 만드는 방법도 가능하다. 상도가 치킨을 구매하는 금액의 최솟값을 구해보자.

입력

첫째 줄에 다섯 정수 A, B, C, X, Y가 주어진다.

출력

양념 치킨 최소 X마리, 후라이드 치킨 최소 Y마리를 구매하는 비용의 최솟값을 출력한다.

접근 방법

X,Y가 구입하는 "최소" 개수라는 것을 주의해야한다. 즉 최소 가격이기만 하면 추가로 더 구매할 수 있다는 것이다. (단 max(X,Y) 보다 많이 구매한다면 최소 가격이 될 수 없음)

양념, 후라이드 각각 구매하는 것 보다 반반을 두마리 구매하는게 더 싸며 X>Y 라고 가정해보자. 

그럼 아래의 1) ~ 2) 사이에서 반반으로 얼마만큼 구매하느냐에 따라 가격이 달라지며, 반복문을 돌면서 최소 가격을 구한다. 

1) Y마리는 반반으로 구매하고,  (X-Y) 마리는 후라이드 치킨 따로 구매.

2) X마리 전부 반반으로 구매

//
//  BF_BOJ16917_양념반후라이드반.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
//X,Y가 구입하는 "최소" 개수라는 것을 주의해야한다.
//즉, X,Y 개 이상 구입할 수 있는 것이다.
//반복문을 돌면서 반반으로 얼마나 구매해야하는지와 그때의 최소 가격을 구한다.

#include <iostream>
using namespace std;

int main(){

    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;
    
    
    bool ischeapBanBan = A+B>2*C ? true : false;    //양념 + 후라이드 각각 사는게 더 싼지 체크
    
    long long mini = 10000000000, sum;
    if(ischeapBanBan){
        
        if(X>Y) {
           
            for(int i = Y; i<=X; i++){
                sum = 2*C*i + (X-i)*A;          //(X-i) : 반반 구매하고 더 구매해야 하는 양념 치킨 수
                if(sum<mini) {mini = sum;}
            }
        }
        else {
            for(int i = X; i<=Y; i++){
                sum = 2*C*i + (Y-i)*B;         //(Y-i) : 반반 구매하고 더 구매해야 하는 후라이드 치킨 수
                if(sum<mini) {mini = sum;}
            }
        }
        
    }
    else{
        mini  = A*X + B*Y;
    }
    
    cout << mini;
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16968

문제

상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.

• 번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.
• 사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.
• 차량 번호판의 형식은 최대 4글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.
• c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.
• 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.

예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.

입력

첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 4보다 작거나 같으며, c와 d로만 이루어져 있다.

출력

첫째 줄에 가능한 차량 번호판의 개수를 출력한다.

접근 방법

완전탐색 문제로 모든 경우의 수를 다 구해주면 된다.

형식을 string 으로 입력받고, 첫 글자 type[0]에 따라 answer 값 초기 설정을 해준다. 

그 후 type[1] 부터 반복문을 돌면서 이전 형식과 일치하는지(연속하는지) 검사하면서 경우의 수를 곱해나간다. 연속하는 경우는 문자일 경우 26-1개를 곱하고, 숫자일 경우 10-1개를 곱한다. 

//
//  BF_BOJ16968_차량번호판1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//
//완전탐색
//이전과 형식 연속되는지만 체크해서 연속되면 해당 글자와 겹치지 않게 1 감소시켜서 곱하기


#include <iostream>
#include <string>

using namespace std;


int main(){
    
    string type;
    cin >> type;
    int answer;
    
    int numD = 10;      //0~9
    int numC = 26;      //a~z
    
    if(type[0]=='c') answer = numC;
    else answer = numD;
    
    for(int i = 1; i<type.length(); i++){       //이전 형식과 연속되는지 검사
        
        if(type[i]=='c'){
            
            if(type[i-1]=='c'){ //연속된 경우 cc
                answer *= (numC-1);
            }
            else{   //dc
                answer *= numC;
            }
        }
            
        else{
            
            if(type[i-1]=='c'){ //cd
                answer *= numD;
            }
            else{   //연속된 경우 dd
                answer *= (numD-1);
            }
        }
        
    }
    
    cout << answer;
    
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/9095

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

접근 방법

DFS 구조의 재귀로 풀었다. 

다른 보통의 문제들과 다른 점은 중복이 허용되기 때문에 visited[] 을 사용하지 않고 풀어야한다는 점이다.

테스트 케이스가 반복되니 테스트케이스 마지막에는 변수들을 초기화해주는 것을 잊지 말자.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int num[3] = {1,2,3};
int cnt = 0;
vector<int> choiceVec;


void sumFunc(int sum){
    
    if(n<sum) return;
    
    if(n==sum){
        cnt++;
        return;
    }
    
    for(int i = 0; i<3; i++){
        
        sum+=num[i];
        choiceVec.push_back(num[i]);
        
        sumFunc(sum);
        choiceVec.pop_back();
        sum-=num[i];
        
    }
    
}


int main(){
    
    int T;
    cin >> T;
    for(int tc = 0; tc<T; tc++){
    
        cin >>n;
        sumFunc(0);
        cout << cnt << "\n";
        
        cnt = 0;
        choiceVec.clear();
        
    }
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/2309

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

접근 방법

재귀를 이용해서 풀었다. DFS와 같은 구조이다. 

9명 중 7명을 뽑아서 toPick이 0이 되었을 때 키를 모두 더해서 키의 합이 100이면 chk를 true로 바꾸서 탐색을 멈췄다.

문제에서 조건을 만족하는 경우 중 아무거나 출력하라 했으니 sum=100이 되는 경우를 찾았을 때 진행을 멈추는 것이 효과적일 것이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


vector<int> heightVec;
bool isVisited[9] = {0};
bool chk = false;
vector<int> ansVec;
int ans = 0;

void Func(int sum, int toPick){
    
    if(toPick==0){
        
        if(sum==100){
            chk = true;
            return;
        }
  
    }
    
    for(int i = 0; i<9; i++){
        
        if(isVisited[i]==0){
            isVisited[i] = 1;
            ansVec.push_back(heightVec[i]);
            sum+=heightVec[i];
        
            Func(sum, toPick-1);
            if(chk){ break;}
            
            sum-=heightVec[i];
            ansVec.pop_back();
            isVisited[i] = 0;
        }
        
    }
    
}


int main(){
    
    
    for(int i = 0; i<9; i++){
        int h;
        cin>>h;
        heightVec.push_back(h);
    }
    
    sort(heightVec.begin(), heightVec.end());
    
    Func(0, 7);
    
    for(int i = 0; i<7; i++){
        cout << ansVec[i] << "\n";
    }
    
    
    return 0;
}