< 백준 BaekJoon : 17520번 Balanced String > C++

 

<< 문제 >>

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

 

 

<< 풀이 >>

 

직접 몇개 만들어보니 규칙이

 - 짝수는 그대로 감

 - 홀수는 이전 거에서 두 배로 감

이렇게 이루어진다. 

 

dp를 통해 풀이해주면 된다. 

 

<< 코드 >>

 

#include <iostream>
using namespace std;

// 3
// 010 011 100 101
// 4
// 0101 0110 1001 1010
// 5
// 01010 01011 01101 01100 10010 10011 10101 10100

int dp[100001];

int main(){
  int n;
  cin >> n;

  dp[1] = 2;
  
  for(int i=2; i<n+1; i++)
  {
    if(i % 2 == 0) { // 짝수인 경우 
      dp[i] = dp[i-1];
    }
    else{ // 홀수인 경우
      dp[i] = (dp[i-1] * 2) % 16769023;
    }
  }

  cout << dp[n];
}

 

 

<< Git Hub >>

 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/17520.%E2%80%85Balanced%E2%80%85String

StudyAlgorithm_Part2/백준/Silver/17520. Balanced String at main · J2on/StudyAlgorithm_Part2