구름톤 챌린지 2주차 - 1

2023.08.21.(월)

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <unordered_map>
#include <algorithm>

using namespace std;

string getString(string & S, int a, int b);

int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N;
    string S;

    cin >> N >> S;

    vector<string> strings;
    set<string> checkDup;

    // 1. 일단 가능한 문자열들 만들어서 vector에 저장하기
    // 언뜻보기엔 (getString에도 반복문이 있어서) O(N^3)이지만, `temp[j-i] = S[j];`가 실행되는 횟수는 대략 1+2+...+N-2 = N(N-1)/2 이라서 O(N^2)임.
    for (int i=0; i<N; i++) {
        for (int end=i; end<N; end++) {
            if (i==0 && end >= N-2) break;
            if (i==1 && end >= N-1) break;
            string temp;
            temp = getString(S, i, end+1);
            if (checkDup.find(temp) == checkDup.end()) {
                strings.emplace_back(temp);
                checkDup.insert(temp);
            }
        }
    }

    // 2. 정렬하기 + 해당 문자열의 점수를 해시 테이블에 저장하기
    sort(strings.begin(), strings.end());
    unordered_map<string, int> scores;
    for (int i=0; i<strings.size(); i++) {
        scores[strings[i]] = i+1;
    }
    
    
    // 3. 다시 조합들을 탐색하며 최댓값을 찾기
    int max = 0;
    for (int i=1; i<N-1; i++) {  // [0,i), [i,j), [j,N) 구간으로 봄
        for (int j=i+1; j<N; j++) {
            string temp;
            int tempSum = 0;
            
            temp = getString(S, 0, i);
            tempSum += scores[temp];
            
            temp = getString(S, i, j);
            tempSum += scores[temp];
            
            temp = getString(S, j, N);
            tempSum += scores[temp];
            
            max = tempSum>max ? tempSum : max;
        }
    }
    
    cout << max;

    return 0;
}

string getString(string & S, int a, int b) { // [a,b)의 문자로 string을 만들어 반환
    string results;
    for (int i=a; i<b; i++) results.push_back(S[i]);
    return results;
}

처음에 문제를 접근할 때 경우의 수가 너무 많이 나오는 것 같아서 dp 방식으로도 생각해봤는데 아무리 생각해도 중복 계산되는 경우의 수가 없어서 그냥 구현하였습니다. (통과함)

문자열 S에서 [a,b) index의 문자들을 뽑아 substring을 만들어 반환하는 함수은 getString 함수를 만들어 사용하였습니다.

문제는 주석에 적힌대로 해결하였습니다. 우선 가능한 S에서 모든 부분문자열을 뽑아내 별도의 vector에 저장하였습니다.

그리고 그 vector를 사전순으로 정렬하고, 그 사전순으로 정렬된 결과에 따라 'scores'라는 해시 테이블을 이용해 각 문자열의 점수를 저장하였습니다.

마지막으로 모든 경우의 수를 다시 돌아보며 가장 높은 점수를 찾아내 출력하였습니다.

 

 

 

---

2023.08.22.(화)

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, K;
    cin >> N >> K;
    
    // #1. 구름 좌표 입력받기
    int temp;
    vector<pair<int,int>> goormCoor;
    vector<vector<bool>> isGoormThere(N, vector<bool>(N, false));
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            cin >> temp;
            if (temp == 1) {
                goormCoor.emplace_back(make_pair(i,j));
                isGoormThere[i][j] = true;
            }
        }
    }
    
    // #2. 구름 좌표의 8방향에 대해 깃발 값을 +1 해두기
    vector<vector<int>> flag(N, vector<int>(N,0));
    int dir[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{-1,1},{1,-1}};
    for (int i=0; i<goormCoor.size(); i++) {
        for (int j=0; j<8; j++) {
            int nx = goormCoor[i].first + dir[j][0];
            int ny = goormCoor[i].second + dir[j][1];
            if (nx>-1 && nx<N && ny>-1 && ny<N && !isGoormThere[nx][ny]) {
                flag[nx][ny]++;
            }
        }
    }
    
    // #3. 깃발 값이 K인 것들의 개수 새기
    int result = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            if (flag[i][j] == K)
                result++;
        }
    }
    
    cout << result;
    
    return 0;
}

우선 #1에서 구름이 있는 좌표를 pair로 vector에 저장합니다. 그리고 #2에서 구름이 있는 좌표를 하나씩 꺼내며, 해당 좌표 기준으로 8방향에 대해 flag[][] 값을 +1 합니다. 즉, #2는 flag의 값을 구하는 과정입니다.

마지막으로 #3에서 flag[][] 배열을 돌아보며 깃발 값이 K인 것들의 개수를 세어 출력합니다.

 

※ 참고 : 왜 pair를 만들 땐 constructor가 아니라 make_pair() 함수를 쓰는 걸까?

 

 

 

---

2023.08.23.(수)

#include <stdio.h>
int main() {
    int N;
    scanf("%d", &N);
    
    int count = 0;
    while (N>=14) {
        N -= 14;
        count++;
    }
    while (N>=7) {
        N -= 7;
        count++;
    }
    while (N>=1) {
        N -= 1;
        count++;
    }
    
    printf("%d", count);
}

N이 음수로 되는 아이템은 사용할 수 없고, 아이템은 최소로 써야합니다. 따라서 반복문을 이용해 통증을 가장 줄여주는 아이템부터 최대한 적용해나가는 방식으로 문제를 해결하였습니다.