문제1. 스도쿠보드

풀이

• 규칙적으로 변하는 수열을 같은수로 나누면 대부분 규칙성을 갖는데, 모든 수에 -1해주고 나눠주면 규칙이 더 잘보인다.(이 문제에서는 -1 시 첫 열이 다 9의 배수가 됨)
• 행 번호
• 이제 십의자리가 0~8이므로 9로 div(/)한 뒤 1을 더해주면 행 번호다
• 열 번호
• 일의자리가 0~8이므로 9로 mod(%)한 뒤 1을 더해주면 열 번호다.
• 그룹 번호
  1. left(해당 행에 존재하는 그룹 중 가장 왼쪽 그룹 번호)를 구한다.
  - 각 행번호 1~3, 4~6, 7~9에 -1후 3으로 나누면 000,111,222가 된다, 여기에 x3 + 1을 하면 111, 444, 777이 나온다.
  2. offset(해당 행에 존재하는 그룹들 중 몇번째 그룹에 속하는지 번호)
  - 각 행번호 1~3, 4~6, 7~9에 -1후 3으로 나누면 000,111,222가 된다, offset 0이면 그대로, 1이면 다음그룹, 2면 다다음그룹
  - 이 둘을 더해서 최종 그룹 번호를 구할 수 있다.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

const int MAX_ROW = 9;//최대 행 크기
const int MAX_COL = 9;//최디 열 크기

class SudokuBoard {
public:
    //칸의 번호로 행 번호 계산 메소드
    int getRowByIndex(int idx) {
        
        //1~n 수열에서는 -1해준 뒤 같은수로 나누면,규칙이 더 잘보임(첫 열이 다 9의 배수)
        //이제 한 행에 존재하는 칸수(MAX_COL)로 나누면 행번호(십의자리)가 나온다.
        return (idx - 1) / MAX_COL + 1;
    }

    //칸의 번호로 열 번호 계산 메소드
    int getColByIndex(int idx) {

        //매 행마다 -1해주면 일의자리가 0~8이 나오고, 한 행에 존재하는 칸수(MAX_COL)로
        //나머지 연산을 하면 해당 칸의 열번호(일의자리)가 나온다.
        return (idx - 1) % MAX_COL + 1;
    }

    //칸의 번호로 그룹 번호 계산 메소드
    int getGroupByIndex(int idx) {
        int r = getRowByIndex(idx);//행 번호
        int c = getColByIndex(idx);//열 번호
        return getGroupByPosition(r, c);//그룹 번호 반환
    }
    
    //칸의 위치(행, 열)로 그룹 번호 계산하는 메소드
    int getGroupByPosition(int row, int column) {

        //각 행번호 1~3, 4~6, 7~9에 -1후 3으로 나누면 000,111,222가 됨
        //여기에 *3 + 1을 하면 111, 444, 777이 나온다.
        //행번호로, 해당 행에 존재하는 그룹 중 가장 왼쪽 그룹 번호
        int left = ((row - 1) / 3) * 3 + 1;

        //각 행번호 1~3, 4~6, 7~9에 -1후 3으로 나누면 000,111,222가 됨
        //offset 0이면 그대로, 1이면 다음그룹, 2면 다다음그룹
        //열번호로, 해당 행에 존재하는 그룹 중 몇번째 그룹에 속하는지 알아냄
        int offset = ((column - 1) / 3);
        
        //1,4,7번 그룹에 offset 더해서 최종 그룹번호 반환
        return left + offset;
    }
    
    //반대로 행, 열로 칸 인덱스 계산하는 메소드
    int getIndexByPosition(int row, int column) {
        //1 행당 9씩 증가하므로 (row-1)*9해서 십의자리 완성
        //(col-1)%9 하면 0~8 나오므로 +1더해서 일의자리 완성
        return (row - 1) * 9 + (column - 1) % 9 + 1;
    }
};

//각 casei의 입력 인덱스가 속한 행, 열, 그룹번호 출력 함수
void process(int i) {
    int idx;
    cin >> idx;//찾을 인덱스 입력

    SudokuBoard board = SudokuBoard();

    int row = board.getRowByIndex(idx);
    int col = board.getColByIndex(idx);
    int group = board.getGroupByIndex(idx);

    //해당 casei의 결과 출력
    printf("Case #%d:\n", i);
    printf("%d %d %d\n", row, col, group);
}

int main() {

    int t;
    cin >> t;

    //case1~ caset까지 반복
    for (int i = 1; i <= t; i++) {
        process(i);
    }

    return 0;
}

문제2. Probing

풀이

• 이 문제는 bool형 카운팅 배열을 사용해 사용중인 행운권 번호인지 확인하는 것이 핵심이다.
• 만약 true 플래그가 있다면, 그 번호는 skip하고 다음 번호를 검사하는 로직을 구현했다.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

class TicketTable {
public:
    vector<bool> used;//사용된 행운권 true인 카운팅 배열
    int size;
    
    TicketTable(int size) {
        this->size = size;//행운권의 수(n)
        this->used.assign(size, false);//length만큼 false로 초기화
    }

    //userId에 대한 미사용된 행운권번호 찾아 반환 함수
    int findEmptyIndexByUserId(int userId) {

        //행운권번호 = 회원번호%n으로 지급
        int num = userId % this->size;
        while (1) {
            //미사용된 행운권 번호면 번호 반환
            if (!this->isEmpty(num)) {
                return num;
            }
            //다음 번호로 증가하되, n-1번째면 다시 0번째부터 검사
            num = (num +1) % this->size;
        }
    }

    //파라미터의 번호가 사용된 번호인지 bool리턴 함수 -> 사용은 안했음
    bool isEmpty(int ticketIndex) {
        return this->used[ticketIndex];
    }

    //1~lenght(n)개 행운권 중 사용한 번호 true로 set
    void setUsed(int ticketId) {
        this->used[ticketId] = true;
    }

};

//행운권 번호 벡터 반환하는 함수
vector<int> getTicketNum(vector<int> ids, int n, int m) {
    vector<int> tickets;

    //행운권 수만큼 생성
    TicketTable table = TicketTable(n);

    for (int i = 0; i < m; i++) {
        //사용가능한 행운권번호 찾아 tickets에 반환
        int ticketIdx = table.findEmptyIndexByUserId(ids[i]);
        tickets.push_back(ticketIdx);
        table.setUsed(ticketIdx);//해당 번호 사용 플래그 on
    }
    return tickets;
}

int main() {

    //행운권 수 n, 회원 수 m 입력
    int n, m;
    cin >> n >> m;

    //m명의 회원번호 입력
    vector<int> ids(m);
    for (int i = 0; i < m; i++) {
        cin >> ids[i];
    }

    //행운권 번호 벡터 리턴
    vector<int> tickets = getTicketNum(ids, n, m);

    //결과 출력
    for (int i = 0; i < tickets.size(); i++) {
        cout << tickets[i] << endl;
    }
  
    return 0;
}

문제3. 소인수분해

풀이

• n의 소인수 == n의 소수인 약수 이므로, n은 소수인 약수들의 곱으로 나타낼 수 있다.
• 표준 소인수분해 알고리즘을 사용해서 해결하는 것이 가장 성능이 좋다.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

//표준 소인수분해 계산 함수
vector<long long> factorize(int n) {

    //소인수들 저장 벡터(소수들의 곱 == 소인수 분해)
    vector<long long> factors;

    //n의 소수인 약수들 구해서 factors에 push_back
    for (int i = 2; i * i <= n; i++) {

        //n을 i로 나눠가며,
        //i가 n의 약수인 동안 계속 push_back(12는 2,2,3이므로 2두번)
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;//n값 i로 나눠 갱신
        }
    }

    //sqrt(n)까지 루프를 다 돌았는데도 n>1이면, 현재 n자체가 소수라는 의미
    //만약 n=12라면, i=2->n=6,i=2->n=3,,i=3->n=1으로 딱 나누어 떨어져
    //마지막 처리 안해줘도 된다.
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

void process(int idx) {
    //자연수 n입력(2이상 ~ 10억이하)
    long long n;
    cin >> n;

    //자연수 n의 소인수 분해된 원소들 벡터에 반환
    vector<long long> factors = factorize(n);

    //공백 구분 결과 출력
    cout << "#" << idx+1 << ":\n";
    for (int i = 0; i < factors.size(); i++) {
        cout << factors[i] << " ";
    }
    cout << "\n";
}

int main() {

    //테스트 케이스 수 t 입력
    int t;
    cin >> t;

    //t개의 소인수 분해할 자연수 입력
    for (int i = 0; i < t; i++) {
        process(i);
    }

    return 0;
}

문제4. 소수세기

풀이

• 이 문제는 에라토스테네스의 체 알고리즘을 사용해 입력 가능한 구간의 소수 벡터를 전처리해두는게 핵심이다.

- 에라토스테네스의 체 알고리즘

• 에라토스테네스의 체 알고리즘 클래스 Sieve를 만들어 전처리할 bool벡터 isPrime을 만든다.
• 생성자로 초기화 할 때는 이 벡터를 최대크기로 assign하고, false로 초기화해둔다.
• 이때 파라미터 m을 받아 m의 소수여부를 반환하는 멤버함수 isPrimeNum()은 읽기 전용인 const함수로 선언해 멤버변수 isPrime을 변경하지 않도록 해줬다.
  => 파라미터를 (const Sieve& sieve)로 받았다면, 이 객체는 const 멤버함수만 호출이 가능하다. 따라서 본 코드에서도 const 함수인 isPrimeNum() 멤버함수를 호출할 수 있는 것이다.
  
• 1번과정에서 모두 true로 체크한 뒤, 0과 1은 소인수가 아니므로 false로 초기화해줘야 한다.
  

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

//에라토스테네스의 체 클래스
class Sieve {
public:
    int maxValue;//입력 자연수의 최댓값
    vector<bool> isPrime;//소수 벡터
    
    //생성자 호출 시 [1,n]의 자연수의 소수 여부 카운팅 배열 생성
    Sieve(int maxValue) {
        this->maxValue = maxValue;
        this->isPrime.assign(maxValue + 1, false);//+1해서 maxValue까지 사용o하게 할당
        this->fillSieve();//에라토스테네스의 체 전처리함수 호출해 소수벡터 채움
    }

    //소수 여부 bool 반환하는 const 함수(객체의 멤버변수를 변경하지 않는 함수)
    bool isPrimeNum(int n) const {
        return this->isPrime[n];
    }

    //isPrime 벡터 전처리 함수(에라토스테네스의 체 알고리즘 사용)
    void fillSieve() {

        //1. 처음에는 모두 소수라고 저장했다가
        isPrime.assign(this->maxValue+1, true);

        //2. 0,1은 소수 아니므로 미리 처리
        this->isPrime[0] = false;
        this->isPrime[1] = false;

        //3. [2,N]사이의 모든 자연수 m에 대해
        for (int m = 2; m <= maxValue; m++) {

            //4. 이미 소수가 아니라고 체크되어 있으면 건너뜀
            if (isPrime[m] == false) {
                continue;
            }

            //5. i로 [m*m,maxValue]구간 탐색하며, 모든 m의 배수를 소수가 아니라고 체크한다. 
            //이때 체크되는 숫자들의 입장에서는 m이 가장 작은 소인수가 된다.
            for (long long i = (long long)m * m; i <= maxValue; i += m) {
                //m*m은 100만(10^6)의 제곱이므로 10^12, int범위 초과이므로 long long
                int idx = (int)i;
                isPrime[idx] = false;
            }
        }
    }
};

//l이상 r이하의 소수들 저장한 벡터 반환 함수
vector<int> getAllPrimeNum(int from, int to, const Sieve& sieve) {
    
    //소수 저장 벡터
    vector<int> primes;

    //[from,to]구간의 소수 i만 push_back
    for (int i = from; i <= to; i++) {
        //메버함수로 소수들만 push_back
        if (sieve.isPrimeNum(i)) {
            primes.push_back(i);
        }
    }
    return primes;
}

//테스트 케이스 수행 함수
void process(int idx, const Sieve& sieve) {
    //자연수 l,r 공백구분 입력(l<=r)
    int l, r;
    cin >> l >> r;

    //sieve의 소수 벡터를 반환
    vector<int> allPrimeNum = getAllPrimeNum(l,r,sieve);

    //이 케이스의 소수 개수 출력
    cout << "Case #" << idx << ":" << endl;
    cout << allPrimeNum.size() << "\n";
}

int main() {

    //에라토스테네스의 체 알고리즘으로 전처리
    const int MAX_VALUE = 1000000;//l,r의 최댓값
    Sieve sieve = Sieve(MAX_VALUE);

    //테스트 케이스 수 t 입력
    int t;
    cin >> t;

    //t개의 소인수 분해할 자연수 입력
    for (int i = 1; i <= t; i++) {
        process(i, sieve);
    }

    return 0;
}

문제5. 전투

풀이

• 이 문제는 문제의 조건대로 train 함수와 canWin함수를 사용하면 쉽게 해결이 가능하다.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

//학생과 악당 싸워서 이기는지 여부 bool 반환 함수
bool canWin(const vector<int>& s, const vector<int>& v) {

    for (int i = 0; i < s.size(); i++) {

        if (s[i] == v[i]) {//비기면 다음부하
            continue;
        }
        else if (s[i] < v[i]) {//악당이 이기면 false
            return false;
        }
        else {//학생이 이기면 true
            return true;
        }
    }
    return true;//마지막까지 비겨서 루프탈출시 학생승
}

//학생벡터 훈련함수(모든 원소 +1)
void train(vector<int>& students) {
    for (int i = 0; i < students.size(); i++) {
        students[i]++;
    }
}

int main() {

    //대결 쌍의 수 입력
    int n;
    cin >> n;

    //n명의 학생과 악당 전투력 입력
    vector<int> students(n);
    for (int i = 0; i < n; i++) {
        cin >> students[i];
    }
    vector<int> villains(n);
    for (int i = 0; i < n; i++) {
        cin >> villains[i];
    }

    //0일차부터 시작
    int date = 0;
    while (1) {

        //학생이 이기면, break로 전투종료
        if (canWin(students, villains)) {
            break;
        }
        //학생이 못이기면, 하루 더 훈련(전체 학생+1)
        else {
            train(students);
            date++;
        }
    }

    //훈련 일수 출력
    cout << date << endl;
    return 0;
}

문제6. 축구

풀이

• 이 문제는 무승부가 발생할 수 있는 경우, 무승부가 발생하지 않는 경우로 나눠야한다.
• 그리고 최소의 득점 1:0으로 승리하고, 최소의 실점 0:1으로 패배하도록 한뒤 나머지 extra득실점이 있다면 첫경기에 몰아준다.

- 무승부가 발생할 수 있는 경우

• case1. 경기수가 1경기인데, 득실점 같은(a==b)경우
  - 경기수가 1경기라면 스코어는 반드시 a:b가 된다. 따라서 득실점이 같다면 무승부 1경기가 나올 수 밖에 없다.
• case2. 득실점 합(a+b)가 경기 수(n)보다 작은 경우
  - 득실점 합(a+b)만큼만 승부를 낼 수 있고 나머지는 0:0으로 무승부가 날 수 밖에 없다.
  - 따라서 b경기만큼 0:1로 패배하고 a경기만큼 1:0으로 승리한 뒤 나머지 n-(a+b) 경기만큼은 0:0 무승부가 발생한다.
  - 무승부가 발생하지 않는 경우
• case3. 득점 a>=n 이고, 실점 b<n인 경우
  - 실점 수 b가 n경기 미만이므로 0:1로 패배하는 수를 b로 설정하고, 1:0으로 승리 수 win을 n-b로 설정한다.
  • win 경기를 1:0으로 승리했으므로 남은 득점 수 extraWin을 a-win으로 두고 첫 승리경기에 몰아준다.
• case4. 득점 a<n 이고, 실점 b>=n인 경우
  - 득점 수 a가 n경기 미만이므로 1:0으로 승리하는 수를 a로 설정하고, 0:1로 패배하는 경기 수를 n-a로 설정한다.
  • 남은 실점 수 extraLose는 b-lose로 설정하고 첫경기에 몰아주면 된다.
• case5. 득실점 합 a+b>n인 경우
  - 이때는 먼저 b경기를 패배한다고 가정한 뒤, 최소 승리 경기 수 win은 max(1경기, n-b경기)로 하여 최소 1경기는 승리하도록 한다.
  • 단 이때 최대 승리 수 win은 최소 1패는 해야 하므로 n-1또는 득점 수 a 만큼만 승리할 수 있으므로 a가 된다.
  • 따라서 앞서 구한 win이 (>n-1 || >a)면 min(n-1,a)로 보정해준다.
  • 그렇게 적절한 win을 정하고 나면 lose=n-win이 되고, extra는 첫경기에 각각 몰아준다.

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

int main() {

    int n, a, b;

    //총 경기 수 n입력
    cin >> n;
    //총 득점 수 a입력
    cin >> a;
    //총 실점 수 b입력
    cin >> b;
    
    //결과 저장 벡터(득:x, 실:y)쌍
    vector<pair<int, int>> result;
    
    //-------------------무승부가 가능한 경우-----------
    //case1. 경기수가 1인경우 어쩔수 없이 결과는 (a,b)
    if (n == 1) {
        result.push_back({ a,b });
        if (a == b) {//득실점 같으면 무승부
            cout << 1 << endl;
        }
        else {
            cout << 0 << endl;
        }
        cout << a << ":" << b << endl;
        return 0;
    }

    //case2. 총 득실점 합이 경기 수보다 작은 경우
    //모든 경기에 최소1골이 나올 수가 없으므로 a+b경기만 승부남
    //나머지는 (0,0)무승부가 되어야 한다.
    if (a + b < n) {
        int nonDraw = a + b;//골이 나오는 경기 수
        int draw = n - nonDraw;//나머지 경기는 어쩔 수 없이 (0,0)

        //a개의 경기를 (1,0)승리
        for (int i = 0; i < a; i++) {
            result.push_back({ 1,0 });
        }
        //b개의 경기를 (0,1)패배
        for (int i = 0; i < b; i++) {
            result.push_back({ 0,1 });
        }
        //남은 경기는 (0,0)
        for (int i = 0; i < draw; i++) {
            result.push_back({ 0,0 });
        }

        //결과 출력
        cout << draw << endl;
        for (auto& p : result) {
            cout << p.first << ":" << p.second << endl;
        }
        return 0;
    }


    //-------------------무승부가 없는 경우-----------
    //case3. 득점a>=n && 실점b<n 
    if (a >= n && b < n) {
        //최소 패배 수는 b(각 패배 경기 최소 (0,1))
        int lose = b;
        int win = n - lose;//나머지는 승리, 최소 (1,0))

        int extraWin = a - win;//남은 한경기는 남은 득점 모두 사용해 승리

        //승리 경기들
        for (int i = 0; i < win; i++) {
            //(남은 득점+1:0)으로 승리
            if (i == 0) {
                result.push_back({ 1 + extraWin, 0 });//
            }
            //(1,0)으로 승리
            else {
                result.push_back({ 1,0 });
            }
        }

        //패배 경기들은 (0,1)로 패배만 가능
        for (int i = 0; i < lose; i++) {
            result.push_back({ 0,1 });
        }

        cout << 0 << endl;
        for (auto& p : result) {
            cout << p.first << ":" << p.second << endl;
        }
        return 0;
    }
    
    //case4, 득점a<n && 실점b>=n 
    if (a < n && b >= n) {
        //우리 득점이 부족하므로 승리 경기 수는 a다. (1,0)으로
        int win = a;
        int lose = n - win;//나머지는 (0,1)로 패배
        int extraLose = b - lose;//남은 실점은 한경기에 몰아서

        //승리 경기들은 (1,0)
        for (int i = 0; i < win; i++) {
            result.push_back({ 1,0 });
        }

        //패배 경기들
        for (int i = 0; i < lose; i++) {
            //(0,남은 실점+1)으로 패배
            if (i == 0) {
                result.push_back({0, extraLose + 1});
            }
            //나머지는 (0,1)로 패배
            else {
                result.push_back({ 0,1 });
            }
        }

        cout << 0 << endl;
        for (auto& p : result) {
            cout << p.first << ":" << p.second << endl;
        }
        return 0;
    }

    //case5. 득실점 합이 경기수보다 큰경우(case3,4에 해당하지 않는 경우)
    if (a + b >= n) {

        int win = max(1, n - b);//최소 승리 수를 결정(최소패배 수 b로 잡고, 최소 1승이상 하도록)
        
        //조건1. 최소 1패는 해야 하므로, 최대 승리 수는 n-1경기
        //조건2. 승리하려면 최소 1골 넣어야 하므로 득점 수 a보다 많이 승리할 수x
        if(win > n-1 || win > a){

            //위 조건 위반하면, 가능한 승리 수를 
            //a(득점 가능한 수)와 n-1(최대 승리 수) 중 더 작은 쪽으로 보정
            win = min(a, n - 1);
        }
        int lose = n - win;//나머지는 패배 경기

        int extraWin = a - win;//승리경기 기본 1골씩 사용후 남은 득점
        int extraloss = b - lose;//패배경기 기본 1골식 실점 후 남은 실점
        
        result.clear();

        //승리 경기 처리
        for (int i = 0; i < win; i++) {
            //첫경기에 extrawin 몰아서배분,
            if (i == 0) {
                result.push_back({ extraWin + 1, 0 });
            }
            //나머지는 (1,0) 승리
            else {
                result.push_back({ 1,0 });
            }
        }

        //패배 경기 처리
        for (int i = 0; i < lose; i++) {
            //첫경기에 extraloss 몰아서 배분,
            if (i == 0) {
                result.push_back({ 0, extraloss + 1 });
            }
            //나머지는 (0,1) 패배
            else {
                result.push_back({ 0,1 });
            }
        }

        //결과 출력
        cout << 0 << endl;
        for (auto& p : result) {
            cout << p.first << ":" << p.second << endl;
        }
        return 0;
    }
    return 0;
}