[0605~0606] 알고리즘

4949. 균형잡힌 세상

  C++ STL에 대해 알아봤으니 대충 써먹어보려고 문제 뒤적이다 1~2년전에 풀다 만 문제를 발견했다... 정작 벡터는 안 쓰고 스택을 썼지만.

#include <iostream>
#include <vector>
#include <stack>
#include <string>

int main()
{
    std::string s;
    bool isChecked = false;

    while (true)
    {
      getline(std::cin, s);

      if (s == ".") break;

      std::stack<char> bracketStack;

      for (int i = 0; i < s.size(); i++)
      {
        if (s[i] == '(' || s[i] == '[')
        {
          bracketStack.push(s[i]);
        }
        else if (s[i] == ')')
        {
          if (bracketStack.empty() || bracketStack.top() != '(')
          {
            std::cout << "no\n";
            isChecked = true;            
            break;
          }
          else 
          {
            bracketStack.pop();
          }
        }
        else if (s[i] == ']')
        {
          if (bracketStack.empty() || bracketStack.top() != '[')
          {
            std::cout << "no\n";
            isChecked = true;
            break;
          }
          else
          {
            bracketStack.pop();
          }
        }        
      }

      if (!isChecked)
      {
        if (bracketStack.empty())
        {
          std::cout << "yes\n";
        }        
        else std::cout << "no\n";
      }

      isChecked = false;      
    }
    
    return 0;
}

* 추가로 알게 된 점 : 위 문제를 풀며 문자열을 입력 받는데, 문자열에 공백이 포함되어 있다보니 아무생각 없이 쓴 std::cin 으로는 공백 이전까지만 문자열을 받아 제대로 된 결과를 얻을 수 없었다. 찾아보니 공백을 포함한 문자열을 받기 위해서는 getline을 쓴다는 듯.

 

 

1010. 다리 놓기

  유독 자꾸 다이내믹 프로그래밍 문제를 골라 푸는 기분인데(...) 진짜 아니다... 그냥 보이길래 풀었다... 이번엔 정말 벡터를 썼다. 대체적인 흐름이나 구성 자체는 전에 풀었던 문제들이랑 비슷한데, 처음으로 벡터를 써서 풀었음 + 제대로 차근차근 코드 구조를 짜면서 세웠음에 만족하기로. Top-down 방식(아마도...)으로 해결했다.

#include <iostream>
#include <vector>

int connectPoint(int n, int m, std::vector<std::vector<int>>& memory);

int main()
{
  std::cin.tie(NULL);
  std::ios_base::sync_with_stdio(false);

  int n, m, testCase;

  std::cin >> testCase;

  for (int i = 0; i < testCase; i++)
  {
    std::cin >> n >> m;
    std::vector<std::vector<int>> memory(n + 1, std::vector<int> (m + 1, 0));
    for (int j = 1; j <= n; j++)
    {
      memory[j][j] = 1;
    }

    std::cout << connectPoint(n, m, memory) << '\n';
  }  

  return 0;
}

int connectPoint(int n, int m, std::vector<std::vector<int>>& memory)
{  
  if (memory[n][m] != 0) 
  {
    return memory[n][m];
  }
  else if (n == 1)
  {
    memory[n][m] = m;
    return memory[n][m];
  }
  else 
  {
    for (int i = 1; i <= m - n + 1; i++)
    {
      memory[n][m] += connectPoint(n - 1, m - i, memory);
    }
    return memory[n][m];
  }  
}

 

---

  흐름을 짜는 것은 생각보다 어렵지 않았는데, 오히려 2차원 벡터를 쓸 줄 몰라서 사용법을 찾느라 헤맸다. 2차원 벡터를 사용할 때는 벡터 선언 시 타입에 또다른 벡터를 넣어주는 방식으로 선언할 수 있다. 

std::vector<std::vector<int>> memory(n + 1, std::vector<int> (m + 1, 0));

  코드의 중간 부분에서 memory 벡터를 선언하는 부분인데, 위 코드는 '모든 원소가 0으로 초기화 된 m + 1짜리 int형 벡터를 담는 n + 1짜리 벡터'를 선언하는 문장이다. 글을 자꾸 안 읽고 쓰려해서 저거 하나 선언하는데 헛발질을 엄청 했다... 어쨌든 벡터 편하다.