JArchive 프로그래밍 일기

문제

수 정렬하기 3 백준 10989

"맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
int n, num;
int arr[10001];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> num; arr[num]++;
  }
  for(int i = 1; i <= 10000; i++){
    while(arr[i]){
      cout << i << '\n'; arr[i]--;
    }
  }
  return 0;
}

리뷰

이 문제는 sort() 함수를 쓰면 틀린다.
왜냐하면 메모리 제한이 8MB 이다.
int 는 4bytes니까. 문제 조건인 천 만개 배열을 선언하면 40MB 를 차지한다.
10000 보다 작은 자연수만 입력으로 들어오니까,
10000을 배열의 인덱스로 두고.
인덱스에 해당하는 숫자의 '개수'를 배열의 값으로 저장해서 해결하면 된다.

문제

소문난 칠공주 백준 1941

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 1941 소문난 칠공주

int room[5][5]; // 입력받음
bool check[25];  // 조합
int temproom[5][5];
bool vis[5][5]; // 방문 체크
int answer;
int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

void checkad(int startx, int starty){

  fill(vis[0], vis[5], 0);

  queue<pair<int,int>> qu;
  qu.push({startx, starty});
  vis[startx][starty] = true;

  int checkcnt = 0;

  while(!qu.empty()){
    int cx = qu.front().X;
    int cy = qu.front().Y;
    qu.pop();
    checkcnt++;

    if(checkcnt==7) break;

    for(int i = 0; i < 4; i++){
      int nx = dx[i] + cx;
      int ny = dy[i] + cy;

      if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;
      if(!vis[nx][ny] && temproom[nx][ny] == 1) {
        vis[nx][ny] = true;
        qu.push({nx, ny});
      }
    }
  }

  if(checkcnt == 7) answer++;
}

void permu(){

  do{
    fill(temproom[0], temproom[5], 0);

    int cnts = 0, startx =0 , starty =0 ;

    for(int i = 0; i < 25; i++){
      if(!check[i]){
        int x = i/5; // 행
        int y = i%5; // 열
        temproom[x][y] = 1; // 선택한 7칸 표시.
        startx = x, starty = y;
        if(1 == room[x][y]) cnts++; // 이다솜파 카운트
      }
    }

    if(cnts >= 4) checkad(startx, starty); // 이다솜파 4명 이상이면 인접 체크 호출

  }while(next_permutation(check, check+25));
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  string st;

  for(int i = 0; i < 5; i++){
    cin >> st;
    for(int j = 0; j < 5; j++){
      if(st[j] == 'Y') room[i][j] = 2;
      else room[i][j] = 1; // S 이다솜파
    }
  }

  for(int i = 7; i < 25; i++) check[i] = true;

  permu();
  cout << answer;

  return 0;
}

리뷰

조합과 bfs가 혼합된 유형이었다.
2차원 배열 fill 함수를 틀리게 구현해서 2시간 동안 고생했다.

로직의 순서는 아래와 같다.

1. 주어진 학생들위치 배열 room에 입력받기
2. false가 7개, true가 18개로 구성된 check 배열 만들기.
3. next_permutation 으로 check배열의 순열을 돌린다. check 배열 false index로 25칸 중에 7칸을 고르는 조합 만들기.
4. 현재 조합 중에서 (선택된 7칸에서) 이다솜파가 4명 이상 포함되어 있는지 검사하기
5. 이다솜파가 4명이상 포함되어 있는 경우에, 선택된 7칸이 서로 모두 인접한지 검사하기.
6. BFS를 돌릴때, 선택된 7개의 칸에 포함되면서도 처음으로 방문한 칸인지 검사해야 한다.

문제

계란으로 계란치기 백준 16987

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
// 16987 계란으로 계란치기

int n, a, b, answer;
vector<pair<int, int>> v;

void dfs(int depth){ // depth == 집어든 계란의 인덱스.

  if(depth == n){
    int crashcnt = 0;
    for(int i = 0; i < n; i++){
      if(v[i].X <= 0) crashcnt++;
    }
    answer = max(answer, crashcnt);
    return;
  }

  // 현재 집어든 계란이 깨졌으면, 그 옆에 다른 계란을 집어든다.
  if(v[depth].X <= 0) dfs(depth+1);
  else {
    bool crashflag = false;
    for (int i = 0; i < n; i++) {
      // i가 현재 집은 계란이거나 이미 깨졌으면 지나감
      if (i == depth || v[i].X <= 0) continue;

      v[i].X -= v[depth].Y;
      v[depth].X -= v[i].Y;

      crashflag = true; // 계란 깼음
      dfs(depth + 1); // 다음 계란을 집는다.

      v[i].X += v[depth].Y;
      v[depth].X += v[i].Y;
    }
    if (!crashflag) dfs(n); // 더이상 깰 계란이 없으면? 개수를 센다.
  }
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i <n; i++){
    cin >> a >> b;
    v.push_back({a,b});
  }

  dfs(0); // 가장 왼쪽(0번째) 계란부터 시작한다.
  cout << answer;
  return 0;
}

리뷰

다시 풀어봐야 할 문제.
백트래킹 카테고리에 있었는데. 문제를 이해 못해서 헤맸다.

집어든 계란을 depth라고 두고, 집어든 계란으로 가능한 많은 계란을 깨면 된다. (공격하면 된다.)
만약 공격할 계란이 남아있지 않거나 내가 집어든 계란이 깨진다면, 집어든 계란을 바꾼다.
집어든 계란을 바꾼다는 의미가 depth를 +1 한다는 의미다.

내가 집어든 계란과 그 계란으로 깰(공격할)계란들이 헷갈려서 갈피를 못잡았다.

문제

암호 만들기 백준 1759

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;

int L, C;
char ch;
vector<int> v;
vector<char> vo = {'a', 'e', 'i', 'o', 'u'};

bool checkvo(string st){
  int mo = 0, ja = 0;
  for(int i = 0; i < L; i++){
    auto it = find(vo.begin(), vo.end(), st[i]);
    if((it - vo.begin()) == vo.size()) {
      ja++;
    }else{
      mo++;
    }
  }

  return (mo > 0 && ja >= 2);
}

void permu(){

  vector<int> tempv(C, 1); // C개 만큼 1 으로 초기화.
  for(int i = 0; i < L; i++){
    tempv[i] = 0;
  } // 선택할 L개만 0으로 초기화

  do{
    string st = "";
    for(int i = 0; i < C; i++){
      if(tempv[i]==0){
        st += v[i];
      }
    }
    if(checkvo(st)){
      cout << st << '\n';
    }
  }while(next_permutation(tempv.begin(), tempv.end()));
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> L >> C; // 선택할 개수, 총 개수

  for(int i = 0; i < C; i++){
    cin >> ch;
    v.push_back(ch);
  }
  sort(v.begin(), v.end());
  permu();

  return 0;
}

리뷰

C개 중에 L개를 선택하도록
{0, 0, 0, 0, 1, 1} 배열을 만들어서 next_permutation() 으로 돌렸다.
길이는 L, 0의 개수는 C개 여야 한다.

0인 자리의 문자를 모아서 string 으로 붙였다.
string 에 모음과 자음 개수를 세서 반환하게 했다.

문제

로또 백준 6603

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;

int k, n;
vector<int> v;

void permu(){

  vector<int> tempv(k, 1); // k만큼 1 으로 초기화.
  for(int i = 0; i < 6; i++){ // 선택할 6개만 0으로 초기화
    tempv[i] = 0;
  } 
  do{
    for(int i = 0; i < tempv.size(); i++){
      if(tempv[i]==0){ // 선택한 6개만 출력 
        cout << v[i] << ' ';
      }
    }
    cout << '\n';
  }while(next_permutation(tempv.begin(), tempv.end()));
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  while(1){
    cin >> k;
    if(k == 0) break;
    v.clear();
    for(int i = 0; i < k; i++){
      cin >> n;
      v.push_back(n);
    }
    permu();
    cout << '\n';
  }
  return 0;
}

리뷰

STL next_permutation() 으로 풀었다.
k개 중에서 6개만 선택한 조합을 출력하는 문제다.

next_permutation()은 사전순으로 마지막인 숫자면 false를 반환해서 멈춘다. 

전체 길이 k가 8이면 반드시 6개만 선택해야 하니깐 0은 6개인 배열을 만든다.
그래서 벡터 tempv를 { 0,0,0,0,0,0,1,1 } 로 시작해야 한다.

0은 선택이고, 1은 선택안하는 것이다.

6개만 0으로 놓고 하면 되겠지 하고 짰는데
{1,1,0,0,0,0,0,0} 이렇게 시작해서 next_permutation()이 아예 동작을 안했었다.

마지막 조합 결과로 시작했기 때문이다.
이거 조심하기!!

문제

N과M(9) 백준 15663

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int num[10];
int arr[10];
bool check[10];

void func(int cnt){ // 이전 수열의 마지막항과 새로 추가할 값이 같으면 중복된 수열이다.
  if(cnt == m){
    for(int i = 0; i < m; i++){
      cout << num[i]<< ' ';
    }
    cout << '\n';
    return;
  }

  int prev_num = -1;

  for(int i = 0; i < n; i++){ // 선택하여 출력할 수를 num에 저장
    if(!check[i] && prev_num != arr[i]){
      check[i] = true;
      num[cnt] = arr[i]; // cnt 번째 숫자를 i로 정한다.
      prev_num = arr[i]; // 방금 선택한 수를 기억해둔다.
      func(cnt+1); // 다음 숫자 탐색 시작
      check[i] = false;
    }
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i <n; i++){
    cin >> arr[i]; // 주어진 수를 arr에 저장
  }

  sort(arr, arr+n); // 정렬. 사전순으로 출력해야하기 때문.
  func(0); // 0번째 수를 선택하는 것으로 시작한다
  return 0;
}

리뷰

백트래킹에 익숙해지기 위한 문제 중 하나다.
수열이 [ 9, 7, 9, 1] 이 주어져도 (1, 9)를 두 번 출력하면 안된다. 하지만 (9, 9)는 출력해야 한다.

일단 수열을 입력받자마자 정렬한다.
이전 선택 값이 현재 선택 값과는 달라야 한다.
그래서 prev_num 변수를 쓴다.

처음에 prev_num 변수를 전역변수로 사용해서 틀렸다.
for문 내부의 함수의 재귀호출이 끝나면 check배열을 false로 돌려놓고, 다음 i번째 숫자를 검사하게 된다.
따라서 방금 종료된 재귀 호출에서 변경된 prev_num이 그대로 적용된다는 문제가 있다.
그래서 동일한 순서(cnt)의 숫자를 선택할 때는 prev_num을 똑같이 바라봐야 한다.
따라서 지역변수로 prev_num을 써야 한다.

문제

하노이 탑 이동 순서 백준 11729

"맞았습니다" 코드

#include <bits/stdc++.h>
using namespace std;

int N; // 원반의 개수

void func(int a, int b, int n){
  if(n == 1) {
    cout << a << ' '<< b << '\n'; // a에서 b로 옮긴다.
    return;
  }
  func(a, 6-a-b, n-1);
  cout << a << ' '<< b << '\n'; // a에서 b로 옮긴다.
  func(6-a-b, b, n-1);
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N;
  cout << (1<<N)-1 << '\n'; // 이동 횟수
  func(1, 3, N);
  return 0;
}

리뷰

재귀를 이용한 하노이탑 이동순서 문제다.
혼자 식 세우기 어려웠다.

기둥 번호가 1,2,3번이 있는데. 번호의 합이 6이다.
그래서 n-1개의 원판을 1번에서 2번으로 옮기고.
n번째 원반을 1번에서 3번으로 옮기는데.
이 때 기둥의 번호를 6에서의 뺄셈을 이용해 표현하는 것이 신기했다.

재귀 공부를 하면서 다시 풀어봐야 할 문제다.