๐Ÿ•๏ธ ICPC Sinchon

[C/C++] ๋ฐฑ์ค€ 1158๋ฒˆ : ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ

์„ ๋‹ฌ 2021. 7. 13. 18:44
๋ฐ˜์‘ํ˜•

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

 

1158๋ฒˆ: ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ

์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

๋ฌธ์ œ

์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ์›์„ ์ด๋ฃจ๋ฉด์„œ ์•‰์•„์žˆ๊ณ , ์–‘์˜ ์ •์ˆ˜ K(≤ N)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด์ œ ์ˆœ์„œ๋Œ€๋กœ K๋ฒˆ์งธ ์‚ฌ๋žŒ์„ ์ œ๊ฑฐํ•œ๋‹ค. ํ•œ ์‚ฌ๋žŒ์ด ์ œ๊ฑฐ๋˜๋ฉด ๋‚จ์€ ์‚ฌ๋žŒ๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ ์›์„ ๋”ฐ๋ผ ์ด ๊ณผ์ •์„ ๊ณ„์†ํ•ด ๋‚˜๊ฐ„๋‹ค. ์ด ๊ณผ์ •์€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ๋ชจ๋‘ ์ œ๊ฑฐ๋  ๋•Œ๊นŒ์ง€ ๊ณ„์†๋œ๋‹ค. ์›์—์„œ ์‚ฌ๋žŒ๋“ค์ด ์ œ๊ฑฐ๋˜๋Š” ์ˆœ์„œ๋ฅผ (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์ด๋ผ๊ณ  ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด (7, 3)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์€ <3, 6, 2, 7, 5, 1, 4>์ด๋‹ค.

N๊ณผ K๊ฐ€ ์ฃผ์–ด์ง€๋ฉด (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 ≤ K ≤ N ≤ 5,000)

์ถœ๋ ฅ

์˜ˆ์ œ์™€ ๊ฐ™์ด ์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

ํ’€์ด

๊ณ ๊ตฐ๋ถ„ํˆฌ

๋”๋ณด๊ธฐ

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(void) {
  ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

  int n,k;
  cin >> n >> k;

  //์ฃผ์–ด์ง„ ๋ฒกํ„ฐ ๋งŒ๋“ค๊ธฐ
  vector <int> v(n);
  for(int i=0; i<n; i++)
    v[i] = i+1;

  //์ถœ๋ ฅํ•  ๋‹ต ๋ฒกํ„ฐ
  vector <int> ans(n);

  //๊ณ„์‚ฐ
  for(int i=n, m=0; i>0; i--, m++){
    if(i==1){
      ans[m] = v[0];
    }
    else if(i<k){
      ans[m] = v[k%i-1];
    }
    else{
      ans[m] = v[k-1];
    }
    
    
    vector <int> nv(i-1);

    //nv ๋ฒกํ„ฐ์— ๊ธฐ์กด ๋ฒกํ„ฐ k ๋‹ค์Œ ๋‚ด์šฉ๋“ค ํ• ๋‹น
    for(int t=0; t<i-1; t++){
      int a = k+t;
      if(a>i-1)
        a = k+t-i;
      
      nv[t] = v[a];
    }

    //๊ธฐ์กด ๋ฒกํ„ฐ์— new ๋ฒกํ„ฐ ํ• ๋‹น
    for(int t=0; t<i-1; t++){
      v[t] = nv[t];
    }
   
  }

  //์ถœ๋ ฅ
  cout << "<";
  for(int i=0; i<n; i++){
    cout << ans[i];
    if(i != n-1)
      cout << ", ";
  }
  cout << ">";

  return 0;
  
}

 

 

์ด ๋ฌธ์ œ์˜ ํฌ์ธํŠธ

1. ๋ฌธ์ œ์—๋Š” ์›์ด๋ผ๊ณ  ์ฃผ์–ด์กŒ์ง€๋งŒ vector์„ ์ด์šฉํ•ด ํ’€์ดํ•˜๊ธฐ ์œ„ํ•ด ์ผ์ž๋กœ ์ƒ๊ฐํ•œ๋‹ค.

2. ์‚ด์•„๋‚จ์€ (์ œ์™ธ๋œ) ์• ๋“ค์€ ๋‹ค์‹œ ๋’ค๋กœ ๊ฐ€์„œ ์ฐจ๋ก€๋ฅผ ๊ธฐ๋‹ค๋ฆฐ๋‹ค.

3. k๋ฒˆ์งธ (ํ˜น์€ nk๋ฒˆ์งธ) ์• ๋“ค์€ ์ œ์™ธ๋œ๋‹ค.

 

#include <iostream>
#include <vector>

using namespace std; 

int main() {
  //์ž…๋ ฅ
  int n,k;
  cin >> n >> k;
	
 
  //๊ณ„์ƒจ
  vector <int> v, ans;
  for (int i=0; i<n; i++)
    v.push_back(i+1);

  for (int t=0,m=0; m<n; t++){
    if(t%k == k-1){
      ans.push_back(v[t]);
      m++;
    }
    else {
      v.push_back(v[t]);
    }
  }

  //์ถœ๋ ฅ
  cout << "<";
  for(int i=0; i<n; i++){
    if(i == n-1){
      cout << ans[i];
      }
    else{
      cout << ans[i] << ", ";
    }
  }
  cout << ">";

  return 0;
}

 

 

 

๋ฐ˜์‘ํ˜•