JArchive 프로그래밍 일기

문제링크

연속된 수들의 합을 구해야한다.

수열의 시작 인덱스 a와 마지막 인덱스 b 를 두고 합이 m이 나오면 개수를 세준다. 

인덱스 a와 b는 같을 수 있다. b는 수열 길이 n 직전까지 증가한다.

계속 다른 수열합을 확인해야 하니까 a와 b 인덱스는 계속 증가한다.

단, a가 b보다 큰 인덱스가 되면 안된다.  a <= b  여야 한다. 

누적 합 sum이 m보다 작다면, 수열의 마지막 인덱스 b를 증가시킨다. 

누적 합 sum이 m보다 크다면, 수열의 시작 인덱스 a를 증가시킨다. 

맞았습니다 코드 링크 

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

ll a, b, sum, n, m, answer;
int arr[10005];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n; i++ ) cin >> arr[i];

  sum = arr[a];
  while(b < n && a <= b){
    if(sum <= m){
      if(sum == m) answer++;
      sum += arr[++b];
    }else { // sum > m
      sum -= arr[a++];
      if(a > b){
        b = a;
        sum = arr[a];
      }
    }
  }
  cout << answer;
  return 0;
}

  for(int k = 0; k < n; k++){ // 거쳐가는 정점
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

int n;
int arr[102][102];

void floyd() {

  for(int k = 0; k < n; k++){ // 거쳐가는 정점
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
      }
    }
  }
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++){
    for(int j = 0; j< n; j++){
      cin >> arr[i][j];
      if(arr[i][j] == 0) arr[i][j] = INF;
    }
  }
  floyd();
  for(int i = 0; i < n; i++){
    for(int j = 0; j< n; j++){
      if(arr[i][j] == INF) cout << 0 << ' ';
      else cout << 1 << ' ';
    }
    cout << '\n';
  }

  return 0;
}

플로이드 와샬 알고리즘 (나동빈님 블로그)

문제

1,2,3 더하기 9095

"맞았습니다"코드

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

int tc, n; // n은 11보다 작은 양수다.
int D[12];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> tc;
  D[1] = 1, D[2] = 2, D[3] = 4;
  for(int i = 4; i <= 11; i++){
    D[i] = D[i-1] + D[i-2] + D[i-3];
  }
  while(tc--){
    cin >> n;   cout << D[n] << '\n';
  }
  return 0;
}

리뷰

점화식 찾는것이 쉽지 않았던 문제다.
D[i] == i를 1,2,3의 합으로 나타내는 방법 개수 라고 정했다.

일단 작은 수를 써보면서 점화식을 도출해봤다.
D[1] = 1개 (1)
D[2] = 2개. (1+1, 2)
D[3] = 4개. (1+2, 2+1, 1+1+1, 3)
D[4] = 7개. (1+1+1+1, 3+1, 2+1+1, 1+2+1, 1+1+2, 1+3, 2+2)

D[3]과 D[4]만 비교해보면.
D[3] = 4개. (1+2, 2+1, 1+1+1, 3)
D[4] = 7개. (1+1+1+1, 3+1, 2+1+1, 1+2+1, 1+1+2, 1+3, 2+2)

D[3]은 3을 만드는 4개 방법이 있다.
(1+2, 2+1, 1+1+1, 3) 이 4개의 방법에 +1만 붙이면 4가 만들어진다.
(1+2 +1, 2+1 +1, 1+1+1 +1, 3 +1)

D[2]은 2을 만드는 2개 방법이 있다.
(1+1, 2) 이 2개 방법에 +2만 하면 4가 만들어진다.
(1+1 +2, 2 +2)

D[1]은 (1) 1개 방법이 있는데. 여기에 +3만하면 4가 만들어진다.

이처럼 D[1], D[2], D[3] 의 방법 개수를 더하면 D[4]가 된다.
D[i] = D[i-1] + D[i-2] + D[i-3]

문제

그림 백준 1926

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
​
int n, m; // 세로, 가로
int board[502][502];
int v[502][502]; // 방문했으면 1로 표시
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
​
int cnt, answer; // 그림 개수와 넓이.
​
int bfs(int a, int b){
​
    queue<pair<int,int> > q;
    int num = 0;
​
    // 방문표시 후, 큐에 넣기.
    v[a][b] = 1;
    q.push({a,b});
​
    while(!q.empty()){
​
        int x = q.front().X;
        int y = q.front().Y;
        q.pop();
        num++;
        for(int i = 0; i < 4; i++){
            int tempX = x + dx[i];
            int tempY = y + dy[i];
​
            if(tempX < 0 || tempX >= n || tempY < 0 || tempY >= m) continue; // 범위 초과는 탈출
            if(v[tempX][tempY] == 1) continue; // 이미 방문한거면 지나감
​
            if(board[tempX][tempY] == 1){ // 그림영역이라면 방문표시 후 큐에 넣기.
                board[tempX][tempY] = 2;
                v[tempX][tempY] = 1;
                q.push({tempX, tempY});
            }
        }
    }
​
    return num;
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    cin >> n >> m;
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            cin >> board[a][b];
        }
    }
​
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
​
            if(board[a][b] == 0 || v[a][b] == 1) continue;
            cnt++; //그림 개수 카운트
            answer = max(answer, bfs(a,b)); // 최대 넓이 찾기 
​
        }
    }
​
    cout << cnt << '\n' << answer;
    return 0;
}

리뷰

BFS 기본 형태의 문제다.

인덱스 확인 후 그림영역에 방문 표시를 한다음에 방문한 좌표를 push()를 해줘야하는데.

그거 하나 틀려서 시간을 많이 잡아먹었다.

문제

듣보잡 백준 1764번

리뷰

문제 이름이 특이해서 도전해봤다. ㅋㅋ

두개의 string 명단을 비교해서 중복되는 string들을 출력하는 프로그램을 만들어야 한다.

N개를 저장한 벡터를 만든 후, 입력받은 string을 찾으려고 했는데 시간초과 났다.

혼자 헤매다가 결국 질문 게시판을 찾아보니 정렬을 하세요 라는 글이 있었다.

정렬을 하면 같은 이름끼리 붙어있을테니까!! 덕분에 풀 수 있었다.

맞은 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> 
using namespace std;

int N, M, cnt; // 듣. 보
int max_len, min_len;
vector<string> v, answer;
string st;

int main(void){

    cin >> N >> M;

    for(int i = 0; i < N+M; i++){ // N+M개 모두 입력받기 
        cin >> st;
        v.push_back(st);
    }

    sort(v.begin(), v.end()); // 정렬 

     for(int i = 0; i < N+M-1; i++){
        if(v[i] == v[i+1]){   // 정렬하면 같은 단어는 붙어있다.  
            answer.push_back(v[i]);
            cnt++;
        }
    }

    cout << cnt << '\n';
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << '\n';
    }
    return 0;
}