문제 풀이 및 생각 과정을 정리한 글입니다
https://www.codetree.ai/missions/5/problems/ya-rock/introduction
세 컵이 있을 때 N번에 걸쳐 a번 종이컵과 b번 종이컵을 교환한 뒤, c번 종이컵을 열어 그 안에 조약돌이 있으면 점수를 얻는 행동을 반복한다
조약돌을 어느 컵에 넣어야 최대 점수를 얻을 수 있을까?
1 ≤ N ≤ 100
1 ≤ a, b, c ≤ 3, a ≠ b
컵이 세개 밖에 없고 N이 충분히 작기 때문에 모든 경우를 테스트한다.
1. 조약돌을 넣을 i번 인덱스 고르는 for문
2. a번과 b번을 교체하는 swap 함수 (⭐️ swap 함수 활용)
3. c번에 조약돌이 있는지 확인하고 count
4. 매번 for문 끝날때 count 최대 구하기
https://www.codetree.ai/missions/5/problems/multiply-two-and-remove-one-number/introduction
N이 작기 때문에 모든 경우를 테스트한다.
1. 두배할 i번 인덱스 고르는 for문
2. 제거할 j번 인덱스 고르는 for문
3. j번 인덱스을 제외하고 새로운 vector에 저장
4. 인접한 숫자간의 차의 합을 구하고 최소 구하기
⭐️ 1번 for문 처음에 2배 했으므로 끝에 나누기 2 해주기
https://www.codetree.ai/missions/5/problems/balance-on-coordinate-plane-2/description
좌표평면 위에 서로 다른 N개의 점이 주어졌을 때, x축 혹은 y축에 평행한 직선 3개로 주어진 모든 점들을 전부 지나게 할 수 있는지를 판단하는 프로그램을 작성해보세요.
1 ≤ N ≤ 20
0 ≤ x, y ≤ 10
선 세개를 그어서 주어진 n개의 점을 다 통과하는지 확인해야한다. 선이 그어지는 범위가 충분히 작기 때문에 완전탐색한다.
1. x축, y축에 그은 선 세개의 모든 경우의 수를 3중 for문을 사용하여 구한다
2. n개의 점을 순환하며 다음을 확인하고 갯수를 센다
- x축에 그은 선 세개 중에 하나가 점을 지나가는 지
- x축에 그은 선 2개와 y축에 그은 선 1개 중에 하나가 점을 지나가는 지
- x축에 그은 선 1개와 y축에 그은 선 2개 중에 하나가 점을 지나가는 지
- y축에 그은 선 3개 중에 하나가 점을 지나가는 지
- 해당 선 세개가 지나는 점 갯수가 N개면 전부 지날 수 있다고 판단한다
https://www.codetree.ai/missions/5/problems/balance-on-coordinate-plane-2/description
https://www.codetree.ai/missions/5/problems/tic-tac-to-as-a-team-2/description
두명이서 팀을 먹는 것이 핵심이다. 게임 판과 개인 번호 범위가 충분히 작기 때문에 두명이서 팀을 먹는 모든 경우의 수를 탐색한다.
1. 이중 for문으로 모든 팀 구성(i,j)를 탐색한다.
2. 승리 조건은 다음과 같다
- 가로 줄에 i,j가 있음
- 세로 줄에 i,j가 있음
- 왼쪽 위에서 오른쪽 아래로 대각선에 i,j가 있음
- 오른쪽 위에서 왼쪽 아래로 대각선에 i,j가 있음
- i,j가 있는지 확인하기 위해서는 i,j를 따로 countI, countJ에 출연 횟수를 세고 countI+countJ==3 이면서 countI>=1 이고 countJ>=1이면 된다.
⭐️ countI+countJ==3: 한줄에 I,J가 둔 수가 정확이 세개있다 = 팀 먹으면 승
⭐️ countI>=1, countJ>=1: i와 j가 최소 1번 출연. i혹은 j 한명이서 3번 나오는건 팀으로 승리하는게 아니다.
https://www.codetree.ai/missions/5/problems/length-of-string-that-does-not-appear/description
2번 이상 등장하지 않는 부분문자열 중 길이가 최솟값인 것을 구해아한다. 즉 길이가 1인 부분문자열부터 모두 탐색해가며 모두 실패하는 문자열 길이를 구하면된다.
1. 모든 부분문자열을 각각의 길에 해당하는 set에 저장한다.
2. for문을 통해 부분문자열을 길이를 탐색하며 해당 set에 저장한 부분문자열이 두번 이상 등장하는지 확인한다.
3. 두번 이상 등장하지 않는 부분문자열을 찾는 즉시 해당 길이를 반환한다.
⭐️ 길이 1부터 확인했기 때문에 제일 먼저 찾은 부분문자열의 길이가 최솟값이다.
set을 사용하지 않고 길이 i 부분문자열 구하는 방법
for(int i=1;i<=n;i++){
bool dup = false;
for(int j=0;j<=n-i;j++){
for(int k=j+1;k<=n-i;k++){
for(int l=0;l<i;l++){
if(s[j+l]==s[k+l]) dup = true;
}
}
}
if(dup==false){
cout << i;
break;
}
}
https://www.codetree.ai/missions/5/problems/max-sum-of-subarray/description
int answer = 0;
for(int i=0;i<n-k+1;i++){
int sum = 0;
for(int j=i;j<i+k;j++){
sum += v[j];
}
answer = max(answer,sum);
}
int cnt = 0;
// 시작
for(int i=0;i<n;i++){
// 끝
for(int j=i;j<n;j++){
int sum = 0;
for(int k=i;k<=j;k++){
sum+=arr[k];
}
// 평균
double avg = (double) sum / (j-i+1);
bool exist = false;
for(int k=i;k<=j;k++){
if(arr[k]==avg){
exist = true;
break;
}
}
if(exist) cnt++;
}
}
cout << cnt;
https://www.codetree.ai/missions/5/problems/candy-in-the-basket-2/description
for(int i=0;i<=MAX_N-2*k;i++){
int cnt = 0;
for(int j=0;j<=2*k;j++){
cnt += arr[i+j];
}
max_cnt = max(max_cnt,cnt);
}
cout << max_cnt;
for(int i=0;i<=MAX_N;i++){
int cnt = 0;
for(int j=i-k;j<=i+k;j++){
if(j>=0 && j<=MAX_N) cnt += arr[j];
}
max_cnt = max(max_cnt,cnt);
}
cout << max_cnt;
#include <iostream>
#include <algorithm>
#define MAX_N 100
#define MAX_M 100
using namespace std;
int n,m;
int arr_n [MAX_N];
int arr_m [MAX_M];
int temp [MAX_M];
int main() {
cin >> n >> m;
for(int i=0;i<n;i++){
cin >> arr_n[i];
}
for(int i=0;i<m;i++){
cin >> arr_m[i];
}
sort(arr_m,arr_m + m); // 수열 B 정렬
int cnt = 0;
for(int i=0;i<n-m+1;i++){
for(int j=0;j<m;j++){
temp[j] = arr_n[i+j];
}
sort(temp,temp+m); // 수열 A를 구간 M으로 탐색하여 담은 수열을 정렬
bool match = true;
for(int k=0;k<m;k++){
if(temp[k]!=arr_m[k]){
match = false;
break;
}
}
if(match) cnt ++;
}
cout << cnt;
return 0;
}
수열 B의 순열이 수열 A 안에 몇개가 있는지 구하면된다. 먼저 모든 순열을 구하고 A의 모든 인덱스를 돌며 찾으려고 했는데 더 빠른 방법이 생각났다.
⭐️ 순열을 구할 필요없이 정렬을 사용하자!
수열의 순열이란 수열안 숫자들을 배치할 수 있는 모든 경우의 수다. 모든 순열을 어느 한 기준 (오름차순 혹은 내림차순)으로 정렬하면 전부 다 같은 결과가 나온다. 따라서 수열 B를 오름차순으로 정렬한 것을 수열 A를 구간 길이 M으로 탐색하여 오름차순으로 정렬한 것을 비교하면 된다!
https://www.codetree.ai/missions/5/problems/ability-of-developer-3/description
#include <iostream>
#define MAX_ARR 6
using namespace std;
int arr[MAX_ARR];
int main() {
int total_sum = 0;
for(int i=0;i<MAX_ARR;i++){
cin >> arr[i];
total_sum+=arr[i];
}
int min_diff = 1e9;
for(int i=0;i<MAX_ARR;i++){
for(int j=i+1;j<MAX_ARR;j++){
for(int k=j+1;k<MAX_ARR;k++){
int sum = arr[i]+arr[j]+arr[k];
min_diff = min (min_diff, abs(total_sum-sum-sum));
}
}
}
cout << min_diff;
return 0;
}
https://www.codetree.ai/missions/5/problems/ability-of-developer-2/explanation
#include <iostream>
#define MAX_ARR 6
using namespace std;
int arr[MAX_ARR];
int main() {
int sum = 0;
for(int i=0;i<MAX_ARR;i++){
cin >> arr[i];
sum += arr[i];
}
int total_min = 1e9;
for(int i=0;i<MAX_ARR;i++){
for(int j=i+1;j<MAX_ARR;j++){
for(int k=j+1;k<MAX_ARR;k++){
for(int l=k+1;l<MAX_ARR;l++){
int sum_one = arr[i]+arr[j];
int sum_two = arr[k]+arr[l];
int sum_three = sum - sum_one - sum_two;
int max_team = max(sum_one,max(sum_two,sum_three));
int min_team = min(sum_one,min(sum_two,sum_three));
total_min = min(total_min, max_team-min_team);
}
}
}
}
cout << total_min;
return 0;
}
#include <iostream>
#define MAX_ARR 6
using namespace std;
int arr[MAX_ARR];
int main() {
int sum = 0;
for(int i=0;i<MAX_ARR;i++){
cin >> arr[i];
sum += arr[i];
}
int total_min = 1e9;
for(int i=0;i<MAX_ARR;i++){
for(int j=0;j<MAX_ARR;j++){
for(int k=0;k<MAX_ARR;k++){
for(int l=0;l<MAX_ARR;l++){
if(i==j || i==k || i== l || j==k || j==l || k==l) continue;
int sum_one = arr[i]+arr[j];
int sum_two = arr[k]+arr[l];
int sum_three = sum - sum_one - sum_two;
int max_team = max(sum_one,max(sum_two,sum_three));
int min_team = min(sum_one,min(sum_two,sum_three));
total_min = min(total_min, max_team-min_team);
}
}
}
}
cout << total_min;
return 0;
}
https://www.codetree.ai/missions/5/problems/awkward-digits-2/description
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main() {
string s;
cin >> s;
int i;
for(i=0;i<s.size();i++){
if(s[i]=='0'){
s[i]='1';
break;
}
}
if(i==s.size()){
s[s.size()-1]='0';
}
int num = 0;
for(int i=0;i<s.size();i++){
num+=(s[s.size()-i-1]-'0')*pow(2,i);
}
cout << num;
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> pii;
int main() {
vector<pii>v;
int n;
cin >> n;
for(int i=0;i<n;i++){
int x,y;
cin >> x >> y;
v.push_back({x,y});
}
int answer = 1e9;
// 건너뛸 점 선택
for(int i=1;i<n-1;i++){
int dist = 0;
int prev = 0;
for(int j=1;j<n;j++){
if(j==i) continue;
dist += abs(v[prev].first - v[j].first) + abs(v[prev].second - v[j].second);
prev = j;
}
answer = min(answer,dist);
}
cout << answer;
return 0;
}
#include <iostream>
using namespace std;
int main() {
int n;
int map[1004];
cin >> n;
for(int i=1;i<=n;i++){
cin >> map[i];
}
int ans = 1e9;
for(int i=1;i<=n;i++){
int dist_sum = 0;
for(int j=1;j<=n;j++){
int dist = (j+n-i)%n;
cout << i << " " << j << " " << dist << endl;
dist_sum+=dist*map[j];
}
ans = min(ans,dist_sum);
}
cout << ans;
return 0;
}
https://www.codetree.ai/missions/5/problems/escaping-carry-2/description
-n개의 숫자가 주어지고, 그 중 정확히 서로 다른 3개의 숫자를 골랐을 때 carry가 전혀 발생하지 않으면서 나올 수 있는 숫자 합의 최댓값을 계산하는 프로그램을 작성해보세요.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
int map[20];
int num;
cin >> n;
for(int i=0;i<n;i++){
cin >> map[i];
}
int answer = -1;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
for(int k=j+1;k<n;k++){
bool carry = false;
//일의 자리
if(map[i]%10+map[j]%10+map[k]%10>=10) carry = true;
//십의 자리
if(map[i]%100/10+map[j]%100/10+map[k]%100/10 >=10) carry = true;
//백의 자리
if(map[i]%1000/100+map[j]%1000/100+map[k]%1000/100>=10) carry = true;
//천의 자리
if(map[i]%10000/1000+map[j]%10000/1000+map[k]%10000/1000>=10) carry = true;
if(!carry) answer = max(answer,map[i]+map[j]+map[k]);
}
}
}
cout << answer;
return 0;
}
#include <iostream>
using namespace std;
int main() {
int map[19][19];
int dx[] = {-1,-1,-1,1,1,1,0,0};
int dy[] = {-1,0,1,-1,0,1,-1,1};
for(int i=0;i<19;i++){
for(int j=0;j<19;j++){
cin >> map[i][j];
}
}
int answer = 0;
for(int i=0;i<19;i++){
for(int j=0;j<19;j++){
if(map[i][j]==0) continue;
for(int k=0;k<8;k++){
int cnt = 1, curI = i, curJ = j;
while(true){
int ni = curI+dy[k];
int nj = curJ+dx[k];
if(nj<0 || nj>=19 || ni<0 || ni>=19) break;
if(map[ni][nj] != map[i][j]) break;
cnt++;
curI = ni;
curJ = nj;
}
if(cnt==5){
cout << map[i][j] << '\n';
cout << i + 2*dy[k] + 1 << " " << j + 2*dx[k] + 1;
return 0;
}
}
}
}
cout << 0;
}
https://www.codetree.ai/missions/5/problems/study-cafe-keeping-distance-5/description
#include <iostream>
#define MAX_N 20
using namespace std;
string seat;
int n;
int main() {
cin >> n;
for(int i=0; i<n; i++){
cin >> seat;
}
int max_count = 0;
for(int i=0;i<n;i++){
if(seat[i]=='1') continue;
seat[i] = '1';
int count = MAX_N;
for(int j=0;j<n;j++){
bool flag = false;
for(int k=j+1;k<n;k++){
if(seat[j] == '1' && seat[k] == '1'){
count = min(count,k-j);
flag = true;
}
if(flag) break;
}
}
max_count = max(max_count,count);
seat[i] = '0';
}
cout << max_count;
return 0;
}