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이 음수로 되는 아이템은 사용할 수 없고, 아이템은 최소로 써야합니다. 따라서 반복문을 이용해 통증을 가장 줄여주는 아이템부터 최대한 적용해나가는 방식으로 문제를 해결하였습니다.
'알고리즘 > 2023 구름톤 챌린지' 카테고리의 다른 글
구름톤 챌린지 2주차 - 2 (2) | 2023.08.27 |
---|---|
구름톤 챌린지 1주차 - 2 (0) | 2023.08.18 |
구름톤 챌린지 1주차 - 1 (0) | 2023.08.16 |