https://www.acmicpc.net/problem/17144

 

17144번: 미세먼지 안녕!

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사

www.acmicpc.net

 

요즘은 시뮬레이션 문제 푸는게 재밌는 것 같다..

복잡한 알고리즘 고민없이 코딩할 수 있어서 그런가,,

 

마냥 구현만 하면 풀 수 있는 문제들이라 아무 생각없이 풀 수 있어 좋은 것 같다(생각없이 풀다보니 코드는 개판이 된다)

 

미세먼지 안녕! 문제는 1) 확산 2) 공기 순환을 구현하면 풀 수 있다.

확산에서 중요한 점은 확산 전 원본 배열을 기준으로 계산을 쭉 진행해야 하기 때문에, 새로운 배열이 필요하다.

나는 memcpy를 이용해 새로운 배열을 만들었고, O(n*2), n 이 1000 이하라 시간안에는 돌아가지만,

예전에 어떤 문제를 풀면서 memcpy가 상당히 느리다는 것을 알았다.. 직접 for문 돌린게 더 빨랐던 것 같기도

 

공기 순환은 rotate 라는 이름(함수 이름 짓기가 젤 어렵다)으로 구현했는데, 사실 실수가 많이 발생할 법한 구현이다.

left, right, up, down 으로 각각 쪼개서 구현해서, 시계방향은 down -> right -> up -> left 순서로 덮어써가고,
반시계방향은  up -> right -> down -> left 순서로 덮어써가면 실수를 줄일 수 있을 것 같다.

 

시뮬레이션 문제의 핵심은 구현 중 발생할 수 있는 실수를 최대한 줄이는게 핵심일 것 같다..

사실 좋은 코드는 실무에서 굉장히 중요하지만, 알고리즘을 풀면서 코드의 질이 크게 중요한 가 싶다 (변명 아님..)

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<string.h>
  3. int arr[1111][1111], r,c,t;
  4. int dy[4] = {-1,1,0,0}, dx[4] = {0,0,-1,1};
  5.  
  6. void rotate(int y, int x, int y_dir){
  7. arr[y+y_dir][x] = 0;
  8.  
  9. for(int i=y+y_dir; i != (y_dir == -1 ? 0 : r-1); i += y_dir){
  10. arr[i][x] = arr[i+y_dir][x];
  11. }
  12.  
  13. int y_ = y_dir == -1 ? 0 : r-1;
  14. for(int i=0; i<c-1; i++){
  15. arr[y_][i] = arr[y_][i+1];
  16. }
  17.  
  18. for(int i=y_; i != y; i-= y_dir){
  19. arr[i][c-1] = arr[i-y_dir][c-1];
  20. }
  21.  
  22. for(int i=c-1; i-1>0; i--){
  23. arr[y][i] = arr[y][i-1];
  24. arr[y][i-1] = 0;
  25. }
  26. }
  27.  
  28. void spread(){
  29. int new_arr[1111][1111] = {0};
  30. memcpy(new_arr, arr, sizeof(arr));
  31. for(int i=0; i<r; i++){
  32. for(int j=0; j<c; j++){
  33. if(arr[i][j] >= 5){
  34. int cnt = 0;
  35. for(int d=0; d<4;d++){
  36. int ny = i+dy[d], nx = j+dx[d];
  37. if(ny>=0 && ny< r&& nx>=0 && nx< c && arr[ny][nx] != -1){
  38. cnt+=1;
  39. new_arr[ny][nx] += arr[i][j]/5;
  40. }
  41. }
  42. new_arr[i][j] -= arr[i][j]/5 * cnt;
  43. }
  44. }
  45. }
  46. memcpy(arr, new_arr, sizeof(arr));
  47. }
  48. int main(){
  49. int src_y = -1;
  50. scanf("%d%d%d", &r,&c,&t);
  51.  
  52. for(int i=0;i<r;i++){
  53. for(int j=0; j<c; j++){
  54. scanf("%d", &arr[i][j]);
  55. }
  56. if(arr[i][0] == -1 && src_y == -1)
  57. src_y = i;
  58. }
  59.  
  60. for(int i=0; i<t; i++){
  61. spread();
  62. rotate(src_y, 0, -1);
  63. rotate(src_y+1, 0, 1);
  64. }
  65. int ans= 0;
  66. for(int i=0;i<r;i++){
  67. for(int j=0; j<c;j++){
  68. ans += arr[i][j];
  69. }
  70. }
  71.  
  72. printf("%d\n", ans+2);
  73. return 0;
  74. }
  75.  

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

https://www.acmicpc.net/problem/14891

 

14891번: 톱니바퀴

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터

www.acmicpc.net

 

위 문제는 시뮬레이션 문제로 자성을 가진 톱니바퀴의 극에 따라 k번 회전 시켰을 때,

톱니바퀴의 변화를 잘 구현해야하는 문제이다.

 

톱니바퀴는 다음과 같이 반시계방향 / 시계방향으로 회전할 수 있다.

 

톱니바퀴의 수는 다음과 같이 4개로 고정돼 있다. 그리고 맞닿아 있는 극이 다를 경우 회전이 영향받는다. 즉, 만약 1 번 톱니바퀴가 반시계방향으로 회전하는 경우 2번째 톱니바퀴의 맞닿아 있는 극이 서로 다르므로, 2번 째 톱니바퀴는 반대방향인 시계방향으로 회전한다. 그리고 2번 톱니바퀴와 3번 톱니바퀴의 맞닿아 있는 극은 같기 때문에 2번이 회전할 때 3번 톱니바퀴는 회전하지 않는다.

 

 

 

그럼 문제는 이해했고, 회전을 어떻게 구현할까.

CPP 에는 rotate 라는 함수를 지원한다. 입력에서 8개의 정수로 N,S 극을 표현하기 때문에, 회전 시 rotate함수로 배열을 적절히 회전시킬 수 있다. 만약 rotate를 사용하지 않는다면, 각 톱니바퀴의 현재 left / right 의 극 index를 저장하는 방법이 있겠다. 

 

개인적으로 시뮬레이션 문제를 풀 때는 직관적인 것이 풀기 편해 rotate를 사용했다.

 

# rotate 사용법

#include <vector>
#include <iostream>
#include <algorithm>
 
auto print = [](auto const& remark, auto const& v) {
    std::cout << remark;
    for (int n: v)
        std::cout << n << ' ';
    std::cout << '\n';
};
 
int main()
{
    std::vector<int> v{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
 
    print("before sort:\t\t", v);
 
    // insertion sort
    for (auto i = v.begin(); i != v.end(); ++i) {
        std::rotate(std::upper_bound(v.begin(), i, *i), i, i+1);
    }
 
    print("after sort:\t\t", v);
 
    // simple rotation to the left
    std::rotate(v.begin(), v.begin() + 1, v.end());
 
    print("simple rotate left:\t", v);
 
    // simple rotation to the right
    std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());
 
    print("simple rotate right:\t", v);
}

Output :

before sort:            2 4 2 0 5 10 7 3 7 1 
after sort:             0 1 2 2 3 4 5 7 7 10 
simple rotate left:     1 2 2 3 4 5 7 7 10 0 
simple rotate right:    0 1 2 2 3 4 5 7 7 10

 

 

k 번 톱니바퀴를 회전 시키는데, 각 회전마다 왼쪽 / 오른쪽 회전이 전파돼야 한다. 

전파를 위해 propagate 함수를 정의 했다. propagate의 역할은 현재 회전한 톱니바퀴의 다음(왼쪽 / 오른쪽) 톱니바퀴의 회전여부를 검사하고, 만약 회전할 경우 그 다음 톱니바퀴로 전파한다.

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #define LEFT_T 6 // 왼쪽 톱니바퀴 index
  6. #define RIGHT_T 2 // 오른쪽 톱니바퀴 index
  7. using namespace std;
  8. int k;
  9. vector< vector<int> >t(4);
  10.  
  11. void left(vector<int>& v){
  12. rotate(v.begin(), v.begin()+1, v.end());
  13. }
  14.  
  15. void right(vector<int>& v){
  16. rotate(v.rbegin(), v.rbegin()+1, v.rend());
  17. }
  18.  
  19. void rotate(vector<int>& v, int t_dir){
  20. if(t_dir == 1) right(v);
  21. else left(v);
  22. }
  23.  
  24. void propagate(int prev_idx, int t_dir, int prop_dir){
  25. // prev_idx : 회전을 전파한 톱니바퀴
  26. // t_dir : 이전 톱니바퀴가 회전한 방향
  27. // prop_dir : propagation의 방향
  28.  
  29. int cur_t = prev_idx + prop_dir;
  30. if(cur_t < 0 || cur_t > 3) return;
  31.  
  32. int prev_tl = t[prev_idx][LEFT_T], prev_tr = t[prev_idx][RIGHT_T];
  33. int cur_tl = t[cur_t][LEFT_T], cur_tr = t[cur_t][RIGHT_T];
  34.  
  35. if(prop_dir == -1){ //left propagation
  36. if(cur_tr != prev_tl){
  37. propagate(cur_t, -t_dir, prop_dir);
  38. } else return;
  39. } else {
  40. if(prev_tr != cur_tl){ // right propagation
  41. propagate(cur_t, -t_dir, prop_dir);
  42. } else return;
  43. }
  44. rotate(t[cur_t], -t_dir);
  45. }
  46.  
  47. int main(){
  48. for(int i=0;i<4;i++){
  49. for(int j=0; j<8; j++){
  50. int m;
  51. scanf("%1d", &m);
  52. t[i].push_back(m);
  53. }
  54. }
  55. scanf("%d", &k);
  56. for(int i=0; i<k; i++){
  57. int cur_t, rot;
  58. scanf("%d%d", &cur_t, &rot);
  59. cur_t -= 1;
  60.  
  61. // 왼쪽 전파
  62. propagate(cur_t, rot, -1);
  63. // 오픈쪽 전파
  64. propagate(cur_t, rot, 1);
  65.  
  66. // 현재 톱니바퀴 회전
  67. rotate(t[cur_t], rot);
  68. }
  69.  
  70. int ans = 0;
  71. for(int i=0;i<4;i++){
  72. ans += t[i][0] << i;
  73. }
  74. printf("%d\n",ans);
  75. return 0;
  76. }
  77.  

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

https://www.acmicpc.net/problem/14503

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

 

위 문제는 시뮬레이션 문제이며, 구현만 잘 하면 쉽게 풀 수 있다.

시뮬레이션 문제를 푸는 것에 있어 가장 중요한 점은 동작과정을 정확히 이해하고, 그대로 구현해야 한다는 점인 것 같다.

 

위 로봇 청소기 문제는 동작은 간단하지만 현재 바라보고 있는 방향이 가장 중요하다.

 

2번 째 행동이 a, b, c, d 4가지 경우가 있는데, 크게 a,b 와 c,d 로 묶을 수 있을 것 같다.

a,b 는 왼쪽 방향으로 돌아가며 순차적으로 탐색해나가는 과정의 조건이고, c,d는 4방향을 모두 탐색한 후의 행동이다.



시뮬레이션 문제에서 동작은 하나씩 모두 잘게 쪼개는 것이 중요하다. 이 문제에서는 현재 바라보는 방향이 가장 중요하므로, 

신경쓰도록 하자.

 

직접 동작을 쪼개보면 알겠지만, 로봇이 c 조건에 부합돼 후진해야 할 때 현재 바라보는 방향처음 진입한 방향의 오른쪽 방향이다. 로봇은 현재 바라보는 방향에서 왼쪽 방향을 탐색하기 때문에 4방향 모두 탐색하는 시점은 3번 회전한 뒤이다.

(처음 북쪽을 봤다면 : 서쪽탐색 후 왼쪽 회전 ->  남쪽 탐색 후 왼쪽 회전 -> 동쪽 탐색 후 왼쪽 회전 -> 북쪽 탐색하면 4방향 모두 탐색조건 부합하므로 현재 방향은 동쪽)

 

d 조건에 부합되는 순간 모든 탐색과정이 종료해야 한다.

 

소스코드

 

  1. #include<stdio.h>
  2. int n,m,src_y, src_x, src_d, arr[55][55];
  3. int dy[4] = {-1,0,1,0}, dx[4] = {0, 1, 0, -1};
  4. int visited[55][55], ans;
  5.  
  6. int turn_left(int d){
  7. return d-1 >= 0 ? d-1 : 3;
  8. }
  9. int solve(int y,int x, int d){
  10. visited[y][x] = 1; // num 1
  11.  
  12. int clean = 0;
  13. for(int i = 0; i < 4; i++){ // num 2
  14. int left = turn_left(d);
  15. int ny = y + dy[left], nx = x + dx[left];
  16. if(!arr[ny][nx] && !visited[ny][nx] && ny >=0 && nx >=0 && nx < m && ny < n){
  17. d = left;
  18. if(solve(ny, nx, d) == -1) return -1;
  19. clean = 1;
  20. } else
  21. d = left;
  22. }
  23. if(!clean){
  24. int ny = y-dy[d], nx= x-dx[d];
  25. if(!arr[ny][nx] && ny >= 0 && nx >= 0 && nx < m && ny < n){
  26. if(solve(ny, nx, d) == -1) return -1;
  27. } else {
  28. return -1;
  29. }
  30. }
  31. return 0;
  32. }
  33. int main(){
  34. scanf("%d%d %d %d %d",&n,&m,&src_y, &src_x, &src_d);
  35. for(int i=0;i<n;i++){
  36. for(int j=0;j<m;j++){
  37. scanf("%d", &arr[i][j]);
  38. }
  39. }
  40.  
  41. solve(src_y, src_x, src_d);
  42.  
  43. for(int i=0; i < n; i++){
  44. for(int j=0; j < m; j++){
  45. ans += visited[i][j];
  46. }
  47. }
  48. printf("%d\n", ans);
  49. return 0;
  50. }

 

 

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17144 미세먼지 안녕  (0) 2021.06.27
BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24

https://www.acmicpc.net/problem/1969

 

1969번: DNA

DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오

www.acmicpc.net

 

이 문제는 brute force 문제이다

 

DNA 염기 { A, C, G, T } 로 구성된 문자열이 N개 주어졌을 때, 각 자리수의 가장 빈도수가 많은 문자만 뽑으면 된다

 

문제에서는 Hamming distance 등 생소한 용어로 혼란을 주지만 문제 자체만 보면 각 자리수의 빈도수가 가장 높은 문자만

 

뽑으면 그것이 전체 DNA sequence 중 가장 차이가 적은 문자열이 된다

 

counting을 위해서 map 자료구조를 이용했고, 사전 순을 맞추기 위해 max 를 검사할 때 사전 순으로 검사하도록 한다

 

 

 

소스코드

 

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<string>
  4. #include<map>
  5. using namespace std;
  6. int n,m;
  7. char buf[55];
  8. char order[4] = { 'A', 'C', 'G', 'T'};
  9.  
  10. int main(){
  11. scanf("%d %d",&n,&m);
  12. vector<string> v;
  13. for(int i=0;i<n;i++){
  14. scanf(" %s", buf);
  15. v.push_back(string(buf));
  16. }
  17. vector< pair<char, int> > ans;
  18. for(int i=0; i<m; i++){
  19. map<char, int> c;
  20. for(int o=0; o<4; o++)
  21. c[order[o]] = 0;
  22. for(int j=0; j<n; j++){
  23. c[v[j][i]] += 1;
  24. }
  25. int max_ = 0, diff = 0;
  26. char d;
  27. for(int o=0; o<4; o++){
  28. diff += c[order[o]];
  29. if(max_ < c[order[o]]){
  30. max_ = c[order[o]];
  31. d = order[o];
  32. }
  33. }
  34. ans.push_back(make_pair(d, diff-max_));
  35. }
  36. int cnt = 0;
  37. for(int i=0;i<ans.size();i++){
  38. printf("%c", ans[i].first);
  39. cnt += ans[i].second;
  40. }
  41. printf("\n%d\n", cnt);
  42. return 0;
  43. }

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 14891 톱니바퀴  (0) 2021.06.12
BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24

https://www.acmicpc.net/problem/2529

 

2529번: 부등호

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제

www.acmicpc.net

 

문제의 조건 

1. k 는 2보다 크거나 같고, 9보다 작거나 같다

2. k+1개의 숫자는 서로 다른 숫자이다

3. k개의 부등호에 맞는 값 중 최대값, 최소값을 구해야 한다

 

 

부등호에 '<=', '>=' 이 존재하고 서로 다른 숫자라는 조건이 없었다면, 경우의 수가 1e10 이 돼 TLE이 나겠지만, 

서로 다른 k+1 개의 수를 찾기 때문에 (k+1)! 의 경우의 수만 찾으면 된다.

 

처음에는 재귀함수를 통해 백트랙킹으로 풀었다.

 

소스코드 (백트랙킹)

숫자가 최대 10개이므로 비트마스크로 사용한 숫자를 체크하며, 조건이 맞지 않으면 재귀를 탈출하고, 

k+1 개의 숫자를 다 채우면 1을 리턴하면서 종료된다.

 

최솟값은 0부터 시작해서 찾아야하고, 최댓값은 9부터 시작해서 내려가며 찾아야하기 때문에

같은 재귀라도 반복문을 달리 사용해야하는 번거로움이 있었다.

 

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string>
  5. using namespace std;
  6. typedef long long ll;
  7. int k;
  8. char karr[11];
  9. string min_="", max_="";
  10. bool inline chk(int a, char c, int b){
  11. return c == '>' ? a>b : a<b;
  12. }
  13. string num(vector<int>& ans){
  14. string s = "";
  15. for(int i=0; i < ans.size(); i++){
  16. s += ans[i] + '0';
  17. }
  18. return s;
  19. }
  20. int solve(vector<int>& ans, int visited, int p, int ismax){
  21. if(p == k) {
  22. return 1;
  23. }
  24. int cur = ans[p];
  25. int init = ismax ? 9 : 0;
  26. int iter = ismax ? -1 : 1;
  27. int end = ismax ? -1 : 10;
  28. for(int pp1=init; pp1 != end; pp1+=iter){
  29. if(visited & (1<<pp1))
  30. continue;
  31.  
  32. if(chk(cur, karr[p], pp1)){
  33. ans.push_back(pp1);
  34. if(solve(ans, visited | (1<<pp1), p+1, ismax))
  35. return 1;
  36. ans.pop_back();
  37. }
  38. }
  39. return 0;
  40. }
  41. string solve_(int i, int ismax){
  42. int visited = 0;
  43. vector<int>ans;
  44.  
  45. ans.push_back(i);
  46. visited |= (1<<i);
  47. if(solve(ans, visited, 0, ismax)){
  48. return num(ans);
  49. }
  50. return "";
  51. }
  52. int main(){
  53. scanf("%d", &k);
  54. for(int i=0;i<k;i++){
  55. scanf(" %c", &karr[i]);
  56. }
  57.  
  58. for(int i=0; i<10; i++){
  59. min_ = solve_(i, 0);
  60. if(min_ != "") break;
  61. }
  62.  
  63. for(int i=9; i>=0; i--){
  64. max_ = solve_(i, 1);
  65. if(max_ != "") break;
  66. }
  67. printf("%s\n%s\n", max_.c_str(), min_.c_str());
  68. return 0;
  69. }

 

 

풀다보니 최소값은 0~k 의 숫자, 최대값은 9~9-k 까지의 숫자만 사용하면 부등호를 만족하는 순서를 찾을 수 있기 때문에,

k 가 9인 경우 최대 10! 까지만 돌기 때문에 조합으로 풀 수 있겠다 생각됐다.

 

 

소스코드 (조합)

조합으로 푸니 코드가 깔끔해졌다.. 진작 이렇게 풀걸

처음부터 조합으로 풀 생각을 할 수 있도록 문제 해결 전략을 잘 세워야겠다..

 

  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<vector>
  4. using namespace std;
  5. int k;
  6. char karr[10];
  7. bool inline chk_(int a, char c, int b){
  8. return c == '>' ? a>b : a<b;
  9. }
  10. int chk(vector<int>& cand){
  11. for(int i=0; i<k; i++){
  12. if(!chk_(cand[i], karr[i], cand[i+1]))
  13. return 0;
  14. }
  15. return 1;
  16. }
  17. int main(){
  18. scanf("%d", &k);
  19. for(int i=0; i<k;i++)
  20. scanf(" %c", &karr[i]);
  21.  
  22. vector<int> min_ = vector<int>(k+1), max_ = vector<int>(k+1);
  23. for(int i=0; i<=k; i++){
  24. min_[i] = i;
  25. max_[i] = 9-i;
  26. }
  27.  
  28. do{
  29. if(chk(min_)) break;
  30. }while(next_permutation(min_.begin(), min_.end()));
  31.  
  32. do{
  33. if(chk(max_)) break;
  34. }while(prev_permutation(max_.begin(), max_.end()));
  35.  
  36. for(int i=0; i<=k; i++)
  37. printf("%d",max_[i]);
  38. printf("\n");
  39. for(int i=0; i<=k; i++)
  40. printf("%d",min_[i]);
  41. printf("\n");
  42. return 0;
  43. }

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 14503 로봇 청소기  (0) 2021.06.12
BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04

www.acmicpc.net/problem/17472

 

17472번: 다리 만들기 2

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.

www.acmicpc.net

 

이 문제는 DFS, MST(최소신장트리) 를 이용해 푸는 문제이다. 질문 게시판을 보니 삼성 코딩테스트 기출문제인듯 하다. 위 문제 풀이 방법 중 핵심은 인접한 셀들을 "섬"으로써 잘 Grouping 하여, 다른 "섬"(group)과의 최단거리를 찾아야 한다

 

일단 필요한 알고리즘들을 생각해보면,

   1. DFS : 섬의 개수 세기

   2. MST(최소신장트리) : 모든 섬들을 연결하는 최단 간선 구하기 

이다.

 

MST 에는 크루스칼(Kruskal) 알고리즘, 프림(prim) 알고리즘이 있다. 

 

크루스칼 알고리즘

간선의 가중치를 정렬해 작은 것 부터 차례로 선택해나가는 방법

1. 간선들을 가중치의 오름차순으로 정렬한다
2. 정렬된 간선 중 사이클을 형성하지 않는 간선을 선택
3. 해당 간선을 현재 MST 집합에 추가
4. 1~3 과정을 "|정점 수| - 1" 번 반복  // V 개의 정점을 연결하기 위해 필요한 간선은 V-1개 이므로

 

 

프림 알고리즘

하나의 정점을 선택해 가장 가중치가 작은 간선들을 차례로 연결해나가는 방법

1.  시작 노드(어떤 노드든 상관없음) 를 MST 집합에 포함
2.  1단계에서 만들어진 MST 집합에 인접한 노드들 중 최소 간선으로 연결된 노드를 선택해 MST 집합에 포함
3.  1~2 과정을 "|정점 수| - 1" 번 반복  // V 개의 정점을 연결하기 위해 필요한 간선은 V-1개 이므

 

 

프림알고리즘의 구현을 위해선 priority_queue(우선순위 큐)가 필요할 수 있지만, 본 문제에서는 간선을 우리가 만들어가며 찾아야하기 때문에 BFS(너비우선탐색)를 통해 찾는 것이 적절하다. 같은 이유로 Kruskal 알고리즘을 사용하기 복잡하다.

 

대략 알고리즘을 설명하면 다음과 같다.

 

1. 섬의 갯수 찾기 (DFS)

    - 각 섬의 Grouping을 위해 ID 를 부여한다.

2. 섬의 갯수-1 번 반복하여 다른 그룹의 섬을 잇는 간선 찾기 (BFS)

    - 1번 섬을 기준으로 BFS를 통해 최단거리의 다른 섬(그룹)을 찾으면 1번 그룹에 병합 (Union-Find 개념)

    * 탐색 할 때는 가로/세로 방향 유지

 

* Union-Find 알고리즘 참고 : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

 

 

소스코드

  1. #include<stdio.h>
  2. #include<vector>
  3. #include<queue>
  4. #include<string.h>
  5. using namespace std;
  6.  
  7. struct node{
  8. pair<int,int> cur;
  9. int cnt_bridge, is_vertical;
  10. node(pair<int,int> cur, int cnt, int is_v) : cur(cur), cnt_bridge(cnt), is_vertical(is_v) {};
  11. };
  12.  
  13. int n,m, dx[4]= { -1,1,0,0}, dy[4] = {0,0,-1,1}, arr[11][11];
  14. bool visited[11][11][2];
  15. vector< pair<int,int> > island[7];
  16.  
  17. void find_island(int idx, int y,int x){
  18. visited[y][x][0] = 1;
  19. island[idx].push_back(make_pair(y,x));
  20. arr[y][x] = idx+1;
  21. for(int i=0;i<4;i++){
  22. int ny = y + dy[i], nx = x+dx[i];
  23. if(ny>=0 && nx >=0 && nx < m && ny < n){
  24. if(!visited[ny][nx][0] && arr[ny][nx]){
  25. find_island(idx, ny, nx);
  26. }
  27. }
  28. }
  29. }
  30.  
  31. void push_queue(queue< node >& q, int island_idx=1){
  32. int idx = island_idx-1; // 1번 그룹
  33.  
  34. for(int i=0; i< island[idx].size(); i++){
  35. q.push(node(island[idx][i], 0, -1));
  36. }
  37. // printf("push queue #%d, queue_size : %d\n", island_idx, q.size());
  38. }
  39.  
  40. void Union(int found_island_idx){
  41. int& idx = found_island_idx;
  42. for(int i=0;i<n; i++){
  43. for(int j=0; j<m;j++){
  44. if(arr[i][j] == idx){
  45. island[0].push_back(make_pair(i,j));
  46. arr[i][j] = 1;
  47. }
  48. }
  49. }
  50.  
  51. // printf("union between 1 and %d\n\n", idx);
  52. // for(int i=0;i<n; i++){
  53. // for(int j=0; j<m;j++){
  54. // printf("%d ",arr[i][j]);
  55. // }
  56. // printf("\n");
  57. // }
  58. }
  59.  
  60. int main(){
  61. scanf("%d%d",&n,&m);
  62. for(int i=0;i<n;i++){
  63. for(int j=0; j<m; j++){
  64. scanf("%d", &arr[i][j]);
  65. }
  66. }
  67. int cnt_island = 0;
  68. for(int i=0; i<n;i++){
  69. for(int j=0; j<m;j++){
  70. if(!visited[i][j][0] && arr[i][j]){
  71. find_island(cnt_island, i,j);
  72. cnt_island += 1;
  73. }
  74. }
  75. }
  76.  
  77. // printf("\n");
  78. // for(int i=0; i<n;i++){
  79. // for(int j=0; j<m;j++){
  80. // printf("%d ", arr[i][j]);
  81. // }
  82. // printf("\n");
  83. // }
  84. // cnt_islend-1 edges are needed to connect all island
  85. int ans = 0, edges = 0;
  86. for(int i=0; i<cnt_island-1; i++){
  87. memset(visited, 0, sizeof(visited));
  88. queue< node > q;
  89. push_queue(q, 1);
  90.  
  91. while(!q.empty()){
  92. node cur = q.front(); q.pop();
  93. int cury = cur.cur.first, curx = cur.cur.second;
  94.  
  95. // another island check
  96. if(arr[cury][curx] > 1 && cur.cnt_bridge >= 2) {
  97. // printf("found another island#%d at (%d,%d): %d\n", arr[cury][curx], cury,curx, cur.cnt_bridge);
  98. int island_idx = arr[cury][curx];
  99. ans += cur.cnt_bridge;
  100. edges += 1;
  101. Union(island_idx);
  102. break;
  103. }
  104.  
  105. // cannot pass through another island
  106. if(arr[cury][curx] > 1){
  107. continue;
  108. }
  109.  
  110. if(cur.is_vertical == -1){
  111. visited[ cury ][ curx ][0] = visited[ cury ][ curx ][1] = 1;
  112. } else {
  113. visited[ cury ][ curx ][cur.is_vertical] = 1;
  114. }
  115.  
  116. // build bridge to search island
  117. for(int d=0; d<4;d++){
  118. int ny = cury + dy[d], nx = curx + dx[d];
  119. if(ny >= 0 && nx >=0 && nx < m && ny < n && arr[ny][nx] != 1 && !visited[ny][nx][cury!=ny]){
  120. if( cur.is_vertical == -1 ){ // all directions
  121. q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), cury != ny));
  122. } else if (cur.is_vertical == 1 && cury != ny){
  123. q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 1));
  124. } else if (cur.is_vertical == 0 && cury == ny) { // horizontal
  125. q.push(node(make_pair(ny,nx), cur.cnt_bridge+(arr[cury][curx] == 0?1:0), 0));
  126. }
  127. }
  128. }
  129. }
  130. }
  131. printf("%d\n", (ans == 0 || edges != cnt_island-1) ? -1 : ans);
  132. return 0;
  133. }
  134.  

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 1969 DNA  (0) 2021.05.24
BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04

www.acmicpc.net/problem/1305

 

1305번: 광고

첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다.

www.acmicpc.net

 

위 문제는 길이가 N 인 광고판에 문자열 길이가 L 인 광고가 왼쪽 쉬프트를 하며 무한히 나타날 때, 가능한 문자열의 최소 길이를 구하는 문제이다. 즉, 광고판 길이가 6이고 현재 광고판의 문자열이 "aabaaa" 일때, 가능한 문자열 후보는 "aaba", "aaab", "abaa", "aabaa", "abaaa" 등 다양하지만, 가장 짧은 길이는 4이다.

 

이 문제는 KMP 알고리즘에서 사용하는 pi 배열을 이용하여 풀 수 있다. pi 배열은 접두사(prefix) 와 접미사(suffix)가 같은 부분 문자열 중 가장 길이가 긴 것을 저장한다.

 

"ABADABC" 라는 문자열이 있을 때, pi는 다음과 같이 저장된다.

i 부분 문자열 pi[i]
0 A 0
1 AB 0
2 ABA 1
3 ABAD 0
4 ABADA 1
5 ABADAB 2
6 ABADABC 0

 

KMP는 이 pi배열을 이용해 문자열 검색의 시간 복잡도를 O( |S| * |P| ), (S : 전체 문자열, P : 전체 문자열에서 찾고자하는 패턴(검색) 문자열) 에서 O( |S|+|P| ) 로 줄이는 알고리즘이다.

 

1305 광고문제는 검색까지는 필요없고, Pi만 배열만 있으면 풀 수 있다.

길이가 N인 광고판과 길이가 L (L <= N) 인 문자열이 있을 때, 앞의 X개의 문자열(진한 파란색)은 광고 문자열 L번째 문자 뒤에 반복된다.

 

즉, N길이의 광고판 문자열에 대해 pi 를 구한 후, N-pi[N]을 구하면 답을 구할 수 있다.

 

 

소스코드

소스는 백준님 풀이 방식을 기반으로 구현했습니다.

  1. #include<iostream>
  2. #include<string>
  3. #include<vector>
  4. using namespace std;
  5.  
  6. vector<int> get_pi_array(string s){
  7. int n = s.size();
  8. vector<int>pi(n);
  9. pi[0] = 0;
  10. int j = 0;
  11. for(int i=1; i < n; i++){
  12. while(j>0 && s[i] != s[j]){
  13. j = pi[j-1];
  14. }
  15. if(s[i] == s[j]){
  16. pi[i] = j + 1;
  17. j += 1;
  18. } else {
  19. pi[i] = 0;
  20. }
  21. }
  22. return pi;
  23. }
  24.  
  25. int main(){
  26. int n;
  27. string s;
  28. cin >> n >> s;
  29. vector<int> pi = get_pi_array(s);
  30. cout << n - pi[n-1] << '\n';
  31. return 0;
  32. }

 

 

관련 사이트:

bowbowbow.tistory.com/6

m.blog.naver.com/kks227/220917078260

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 2529 부등호  (0) 2021.05.19
BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04

https://www.acmicpc.net/problem/10826

 

10826번: 피보나치 수 4

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 ��

www.acmicpc.net

 

이 문제는 BOJ2407 조합 문제와 같이 피보나치 10000 의 자릿수가 2000 이 넘어가기 때문에 c++ 표준 자료형의 범위로는 표현할 수 없다. 마찬가지로 string 덧셈으로 풀 수 있는데, 이전 BOJ2407 번에서 구현한 string 덧셈이 비효율적이라 시간초과가 난다. 따라서 string 덧셈과정에서 역순으로 += 연산을 최대한 이용할 수 있도록 구현하여 시간제한 안에 풀 수 있도록 구현하였다.

 

새롭게 안 사실인데, 피보나치 4 문제의 질문 게시글 에서 문자열의 덧셈 방법 s = s + "string" 과 s += "string" 이 다르다는 것을 설명한다. 첫 번째 방법(s = s + "string") 은 string 을 새롭게 복사하기 때문에 O(s.size()^2) 의 시간이 걸린다고 한다. 두 번째 방법은 단순히 이어 붙이기 때문에, 시간적으로 매우 차이가 날 수 있다.

 

 

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
 
string s_add(string s1, string s2){
    string ret = "";
 
    int s1len = s1.length(), s2len = s2.length();
    int is_carry = 0;
    int i;
    for(i = 0; i<s2len; i++){
        char s = s1[i]-'0' + s2[i] + is_carry;
        if(s > '9'){
            is_carry = 1;
            s -= 10;
        } else {
            is_carry = 0;
        }
        ret += s;
    }
 
    for(int j=i; j<s1len; j++){
        char s = s1[j] + is_carry;
        if(s > '9'){
            is_carry = 1;
            s -= 10;
        } else {
            is_carry = 0;
        }
        ret += s;
    }
 
    if(is_carry){
        ret += "1";
    }
    return ret;
}
vector< string >v(10001);
int main(){
    int n;
    cin>>n;
    for(int i=0; i<=10000; i++){
        v[i] = "0";
    }
    v[2= v[1= "1";
    for(int i=3; i<=10000;i++){
        v[i] = s_add(v[i-1], v[i-2]);
    }
    reverse(v[n].begin(), v[n].end());
    cout<< v[n] <<endl;
    return 0;
}
cs

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 17472 다리만들기 2  (0) 2020.11.24
BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03

https://www.acmicpc.net/problem/1516

 

1516번: 게임 개발

첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부

www.acmicpc.net

 

이 문제는 위상정렬로 풀 수 있는 문제이다. 위상 정렬은 주로 게임에서 스킬트리와 같은 즉, 선행되어야 하는 작업이 있을 때의 순서를 어떻게 처리해야 빠른지를 풀 때 사용하는 알고리즘이다. 위상정렬의 구현은 그래프 구조에서 in-direction 의 갯수를 저장하는 배열이 가장 핵심이다. 즉 어떤 노드 K 번에 들어오는 간선의 수가 3개가 있을 때, ind[K] = 3 처럼 저장한 뒤, ind[i] 값이 0인 정점부터 큐(queue)에 넣고 순차적으로 탐색해가면 된다.

 

 

위 그림으로 설명하면

 1. ind 값이 0 인 1번 3번 노드가 queue에 넣는다.
 2. 큐에 가장 앞에 있는 노드를 방문(1 번) 한 후, 이 노드에 연결된 (2 번으로의)간선을 돌면서 ind[ graph[cur][next] ] 의 값을 -1 해준다.
     ( 그림에선 2번으로의 간선이므로, ind[2]--; )
 3. 만약 2번의 과정을 통해서 ind 값이 0 이 되면(ind[ graph[cur][next] ] == 0) 해당 노드를 queue에 push 한다.
 4. 2~3번을 반복

 

 

 

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#include<queue>
#include<vector>
 
using namespace std;
int inline max(int a, int b){return a>b?a:b;}
int n, t[501], ind[501], ans[501];
vector<int> v[501];
 
int main(){
    scanf("%d"&n);
    int p;
    for(int i=1;i<=n;i++){
        scanf("%d"&t[i]);
        while(scanf("%d"&p) == 1){
            if(p == -1break;
            v[p].push_back(i);
            ind[i]++;
        }
    }
 
    queue< pair<intint> > q;
    for(int i=1;i<=n;i++){
        if(ind[i] == 0){
            q.push(make_pair(i, t[i]));
            ans[i] = t[i];
        }
    }
 
    while(!q.empty()){
        int cur = q.front().first; 
        int curt = q.front().second;
        q.pop();
        for(int i=0; i<v[cur].size(); i++){
            ind[ v[cur][i] ]--;
            ans[ v[cur][i] ] = max(ans[v[cur][i]], curt + t[ v[cur][i] ]);
            if(ind[ v[cur][i] ] == 0){
                q.push(make_pair(v[cur][i], ans[ v[cur][i] ] ));
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}
 
 
cs

 

 

 

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 1305 광고  (0) 2020.09.24
BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03
BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02

https://www.acmicpc.net/problem/2407

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net

 

이 문제는 100 C 50 조합 값이 long long int 를 벗어나는 약 30자리 수 정도이기 때문에, 다른 방법으로 덧셈을 계산해야 한다. 따라서 덧셈을 위해 string 클래스를 이용해 문자열끼리의 더하기를 구현하였다.

 

다음은 100_C_n 의 조합의 결과 : 

(100C1) : 1 + 99 = 100
(100C2) : 99 + 4851 = 4950
(100C3) : 4851 + 156849 = 161700
(100C4) : 156849 + 3764376 = 3921225
(100C5) : 3764376 + 71523144 = 75287520
(100C6) : 71523144 + 1120529256 = 1192052400
(100C7) : 1120529256 + 14887031544 = 16007560800
(100C8) : 14887031544 + 171200862756 = 186087894300
(100C9) : 171200862756 + 1731030945644 = 1902231808400
(100C10) : 1731030945644 + 15579278510796 = 17310309456440
(100C11) : 15579278510796 + 126050526132804 = 141629804643600
(100C12) : 126050526132804 + 924370524973896 = 1050421051106700
(100C13) : 924370524973896 + 6186171974825304 = 7110542499799200
(100C14) : 6186171974825304 + 38000770702498296 = 44186942677323600
(100C15) : 38000770702498296 + 215337700647490344 = 253338471349988640
(100C16) : 215337700647490344 + 1130522928399324306 = 1345860629046814650
(100C17) : 1130522928399324306 + 5519611944537877494 = 6650134872937201800
(100C18) : 5519611944537877494 + 25144898858450330806 = 30664510802988208300
(100C19) : 25144898858450330806 + 107196674080761936594 = 132341572939212267400
(100C20) : 107196674080761936594 + 428786696323047746376 = 535983370403809682970
(100C21) : 428786696323047746376 + 1613054714739084379224 = 2041841411062132125600
(100C22) : 1613054714739084379224 + 5719012170438571889976 = 7332066885177656269200
(100C23) : 5719012170438571889976 + 19146258135816088501224 = 24865270306254660391200
(100C24) : 19146258135816088501224 + 60629817430084280253876 = 79776075565900368755100
(100C25) : 60629817430084280253876 + 181889452290252840761628 = 242519269720337121015504
(100C26) : 181889452290252840761628 + 517685364210719623706172 = 699574816500972464467800
(100C27) : 517685364210719623706172 + 1399667836569723427057428 = 1917353200780443050763600
(100C28) : 1399667836569723427057428 + 3599145865465003098147672 = 4998813702034726525205100
(100C29) : 3599145865465003098147672 + 8811701946483283447189128 = 12410847811948286545336800
(100C30) : 8811701946483283447189128 + 20560637875127661376774632 = 29372339821610944823963760
(100C31) : 20560637875127661376774632 + 45764000431735762419272568 = 66324638306863423796047200
(100C32) : 45764000431735762419272568 + 97248500917438495140954207 = 143012501349174257560226775
(100C33) : 97248500917438495140954207 + 197443926105102399225573693 = 294692427022540894366527900
(100C34) : 197443926105102399225573693 + 383273503615787010261407757 = 580717429720889409486981450
(100C35) : 383273503615787010261407757 + 711793649572175876199757263 = 1095067153187962886461165020
(100C36) : 711793649572175876199757263 + 1265410932572757113244012912 = 1977204582144932989443770175
(100C37) : 1265410932572757113244012912 + 2154618614921181030658724688 = 3420029547493938143902737600
(100C38) : 2154618614921181030658724688 + 3515430371713505892127392912 = 5670048986634686922786117600
(100C39) : 3515430371713505892127392912 + 5498493658321124600506947888 = 9013924030034630492634340800
(100C40) : 5498493658321124600506947888 + 8247740487481686900760421832 = 13746234145802811501267369720
(100C41) : 8247740487481686900760421832 + 11868699725888281149874753368 = 20116440213369968050635175200
(100C42) : 11868699725888281149874753368 + 16390109145274293016493707032 = 28258808871162574166368460400
(100C43) : 16390109145274293016493707032 + 21726423750712434928840495368 = 38116532895986727945334202400
(100C44) : 21726423750712434928840495368 + 27651812046361280818524266832 = 49378235797073715747364762200
(100C45) : 27651812046361280818524266832 + 33796659167774898778196326128 = 61448471214136179596720592960
(100C46) : 33796659167774898778196326128 + 39674339023040098565708730672 = 73470998190814997343905056800
(100C47) : 39674339023040098565708730672 + 44739148260023940935799206928 = 84413487283064039501507937600
(100C48) : 44739148260023940935799206928 + 48467410615025936013782474172 = 93206558875049876949581681100
(100C49) : 48467410615025936013782474172 + 50445672272782096667406248628 = 98913082887808032681188722800
(100C50) : 50445672272782096667406248628 + 50445672272782096667406248628 = 100891344545564193334812497256
(100C51) : 50445672272782096667406248628 + 48467410615025936013782474172 = 98913082887808032681188722800
(100C52) : 48467410615025936013782474172 + 44739148260023940935799206928 = 93206558875049876949581681100
(100C53) : 44739148260023940935799206928 + 39674339023040098565708730672 = 84413487283064039501507937600
(100C54) : 39674339023040098565708730672 + 33796659167774898778196326128 = 73470998190814997343905056800
(100C55) : 33796659167774898778196326128 + 27651812046361280818524266832 = 61448471214136179596720592960
(100C56) : 27651812046361280818524266832 + 21726423750712434928840495368 = 49378235797073715747364762200
(100C57) : 21726423750712434928840495368 + 16390109145274293016493707032 = 38116532895986727945334202400
(100C58) : 16390109145274293016493707032 + 11868699725888281149874753368 = 28258808871162574166368460400
(100C59) : 11868699725888281149874753368 + 8247740487481686900760421832 = 20116440213369968050635175200
(100C60) : 8247740487481686900760421832 + 5498493658321124600506947888 = 13746234145802811501267369720
(100C61) : 5498493658321124600506947888 + 3515430371713505892127392912 = 9013924030034630492634340800
(100C62) : 3515430371713505892127392912 + 2154618614921181030658724688 = 5670048986634686922786117600
(100C63) : 2154618614921181030658724688 + 1265410932572757113244012912 = 3420029547493938143902737600
(100C64) : 1265410932572757113244012912 + 711793649572175876199757263 = 1977204582144932989443770175
(100C65) : 711793649572175876199757263 + 383273503615787010261407757 = 1095067153187962886461165020
(100C66) : 383273503615787010261407757 + 197443926105102399225573693 = 580717429720889409486981450
(100C67) : 197443926105102399225573693 + 97248500917438495140954207 = 294692427022540894366527900
(100C68) : 97248500917438495140954207 + 45764000431735762419272568 = 143012501349174257560226775
(100C69) : 45764000431735762419272568 + 20560637875127661376774632 = 66324638306863423796047200
(100C70) : 20560637875127661376774632 + 8811701946483283447189128 = 29372339821610944823963760
(100C71) : 8811701946483283447189128 + 3599145865465003098147672 = 12410847811948286545336800
(100C72) : 3599145865465003098147672 + 1399667836569723427057428 = 4998813702034726525205100
(100C73) : 1399667836569723427057428 + 517685364210719623706172 = 1917353200780443050763600
(100C74) : 517685364210719623706172 + 181889452290252840761628 = 699574816500972464467800
(100C75) : 181889452290252840761628 + 60629817430084280253876 = 242519269720337121015504
(100C76) : 60629817430084280253876 + 19146258135816088501224 = 79776075565900368755100
(100C77) : 19146258135816088501224 + 5719012170438571889976 = 24865270306254660391200
(100C78) : 5719012170438571889976 + 1613054714739084379224 = 7332066885177656269200
(100C79) : 1613054714739084379224 + 428786696323047746376 = 2041841411062132125600
(100C80) : 428786696323047746376 + 107196674080761936594 = 535983370403809682970
(100C81) : 107196674080761936594 + 25144898858450330806 = 132341572939212267400
(100C82) : 25144898858450330806 + 5519611944537877494 = 30664510802988208300
(100C83) : 5519611944537877494 + 1130522928399324306 = 6650134872937201800
(100C84) : 1130522928399324306 + 215337700647490344 = 1345860629046814650
(100C85) : 215337700647490344 + 38000770702498296 = 253338471349988640
(100C86) : 38000770702498296 + 6186171974825304 = 44186942677323600
(100C87) : 6186171974825304 + 924370524973896 = 7110542499799200
(100C88) : 924370524973896 + 126050526132804 = 1050421051106700
(100C89) : 126050526132804 + 15579278510796 = 141629804643600
(100C90) : 15579278510796 + 1731030945644 = 17310309456440
(100C91) : 1731030945644 + 171200862756 = 1902231808400
(100C92) : 171200862756 + 14887031544 = 186087894300
(100C93) : 14887031544 + 1120529256 = 16007560800
(100C94) : 1120529256 + 71523144 = 1192052400
(100C95) : 71523144 + 3764376 = 75287520
(100C96) : 3764376 + 156849 = 3921225
(100C97) : 156849 + 4851 = 161700
(100C98) : 4851 + 99 = 4950
(100C99) : 99 + 1 = 100

 

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;
int n,m;
vector< string > dp[101];
 
string s_add(string s1, string s2){
    string ret = "";
 
    int s1len = s1.length()-1, s2len = s2.length()-1;
    int is_carry = 0;
    while( s1len >= 0 || s2len >= 0){
        int s = ( s1len >= 0 ? s1[s1len]-'0' : 0 ) + ( s2len >= 0 ? s2[s2len]-'0' : 0+ is_carry;
        is_carry = s / 10;
        s %= 10;
 
        ret = (char)(s+'0'+ ret;
        s1len--, s2len--;
    }
    if(is_carry){
        ret = (char)('0'+is_carry) + ret;
    }
    return ret;
}
 
int main(){
    scanf("%d %d",&n,&m);
    
    for(int i=1; i<=n; i++){
        dp[i].resize(n+1);
        for(int j=1;j<n;j++){
            dp[i][j] = "0";
        }
        dp[i][0= dp[i][i] = "1";
    }
    for(int i=2; i<= n; i++){
        for(int j=1; j < i; j++){
            dp[i][j] = s_add(dp[i-1][j-1], dp[i-1][j]);
            // printf("(%dC%d) : %s + %s = %s\n", i,j, dp[i-1][j-1].c_str(), dp[i-1][j].c_str(), dp[i][j].c_str());
        }
    }
    printf("%s\n", dp[n][m].c_str());
    return 0;
}
cs

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

BOJ 10826 피보나치 수 4  (0) 2020.09.04
1516 게임 개발  (0) 2020.09.04
BOJ 2407 조합  (0) 2020.09.04
LCS 최장 공통 부분 수열  (0) 2020.09.03
BOJ 가장 긴 증가하는 부분 수열  (0) 2020.09.02
BOJ 4811 알약  (0) 2020.08.28

+ Recent posts