BOJ - 괄호 추가하기 3(16639)

-
링크

dp로 풀이하려다 막혀 시간복잡도를 계산해 보니
10! * 20 = 7천만 정도로 가능할 것 같아 Brute Force로 풀이했다.

숫자를 담을 벡터와 연산자를 담을 벡터를 따로 두고 Brute Force를 진행한다.

1 + 3 + 5 + 7

위와 같은 식이 있다면,
숫자 벡터엔 1 3 5 7 , 연산자 벡터엔 + + + 이 처음에 들어가 있게 된다.

연속된 두 개의 숫자, 중간의 연산자를 묶어 계산한 뒤, 벡터를 복사하여 넘겨주는 식으로 진행한다.

1. 4 5 7 , + +
2. 1 8 7 , + +
3. 1 3 12 , + +

위 작업을 숫자 벡터의 크기가 1이 될 때까지 하고, max값을 갱신한다.

dp 풀이:

https://www.acmicpc.net/problem/11066 (파일 합치기)

위 문제와 비슷한 방법으로 풀이한다.

maxdp[i][j] = i ~ j 까지의 최댓값
mindp[i][j] = i ~ j 까지의 최솟값

위 두 배열을 이용하여, i ~ j 가 작은 범위부터 0 ~ n 범위까지 구해가면 된다.

이 때, 음수로 인해 4가지 경우에 대해 모두 연산을 해 주어야 한다.
(음수(최소) * 음수(최소) -> 최대일 수도 있기 때문)

최대, 최대
최대, 최소
최소, 최대
최소, 최소

Brute Force 풀이


#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vii vector<pii>
#define IMAX 2000000001
#define LMAX 1000000000000000000
#define DMAX 0xFFFFFFFFFFFFF
int mv1[4] = { 0, 1, 0, -1 };
int mv2[4] = { 1, 0, -1, 0 };
int mv_all1[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
int mv_all2[8] = { 1, 0, -1, 0 , -1, 1, -1, 1 };

int n;
string str;
ll maxV = -LMAX;

ll calculate(char op, ll n1, ll n2) {
 if (op == '+')
  return n1 + n2;
 else if (op == '-')
  return n1 - n2;
 else
  return n1 * n2;
}

void recul(vector<ll> num, vector<char> oper) {

 if (num.size() == 1) {
  maxV = max(maxV, num[0]);
  return;
 }

 for (int i = 0; i < oper.size(); i++)
 {
  ll res = calculate(oper[i], num[i], num[i + 1]);

  vector<ll> nextNum;
  vector<char> nextOper;

  for (int j = 0; j < i; j++)
  {
   nextNum.push_back(num[j]);
  }

  nextNum.push_back(res);

  for (int j = i + 2; j < num.size(); j++)
  {
   nextNum.push_back(num[j]);
  }

  for (int j = 0; j < oper.size(); j++)
  {
   if (i != j)
    nextOper.push_back(oper[j]);
  }

  recul(nextNum, nextOper);
 }
}

int main(void) {
 FIO;

 cin >> n >> str;

 vector<char> oper;
 vector<ll> num;

 for (int i = 0; i < str.size(); i++)
 {
  if (str[i] >= '0' && str[i] <= '9') {
   num.push_back(str[i] - '0');
  }
  else {
   oper.push_back(str[i]);
  }
 }

 recul(num, oper);

 cout << maxV;
}

DP 풀이

 
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pii pair<int, int>
#define pdd pair<double, double>
#define pic pair<int, char>
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vii vector<pii>
#define IMAX 2000000001
#define LMAX 1000000000000000000
#define DMAX 0xFFFFFFFFFFFFF
int mv1[4] = { 0, 1, 0, -1 };
int mv2[4] = { 1, 0, -1, 0 };
int mv_all1[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };
int mv_all2[8] = { 1, 0, -1, 0 , -1, 1, -1, 1 };

int n;
string str;
ll maxdp[19][19];
ll mindp[19][19];

ll calculate(char op, ll n1, ll n2) {
 if (op == '+')
  return n1 + n2;
 else if (op == '-')
  return n1 - n2;
 else
  return n1 * n2;
}

int main(void) {
 FIO;

 cin >> n >> str;

 for (int i = 0; i < n; i++)
 {
  for (int j = 0; j < n; j++)
  {
   maxdp[i][j] = -LMAX;
   mindp[i][j] = LMAX;
   if (i == j && i % 2 == 0) {
    maxdp[i][j] = str[i] - '0';
    mindp[i][j] = str[i] - '0';
   }
  }
 }

 for (int range = 2; range < n; range += 2)
 {
  for (int s = 0; s + range < n; s += 2)
  {
   int e = s + range;

   ll maxV = -LMAX;
   ll minV = LMAX;

   if (range == 2) {
    maxV = calculate(str[s + 1], str[s] - '0', str[e] - '0');
    minV = calculate(str[s + 1], str[s] - '0', str[e] - '0');
   }
   else {
    for (int mid = s + 1; mid < e; mid += 2)
    {
     maxV = max(maxV, calculate(str[mid], maxdp[s][mid - 1], maxdp[mid + 1][e]));
     maxV = max(maxV, calculate(str[mid], mindp[s][mid - 1], mindp[mid + 1][e]));
     maxV = max(maxV, calculate(str[mid], mindp[s][mid - 1], maxdp[mid + 1][e]));
     maxV = max(maxV, calculate(str[mid], maxdp[s][mid - 1], mindp[mid + 1][e]));

     minV = min(minV, calculate(str[mid], maxdp[s][mid - 1], maxdp[mid + 1][e]));
     minV = min(minV, calculate(str[mid], mindp[s][mid - 1], mindp[mid + 1][e]));
     minV = min(minV, calculate(str[mid], mindp[s][mid - 1], maxdp[mid + 1][e]));
     minV = min(minV, calculate(str[mid], maxdp[s][mid - 1], mindp[mid + 1][e]));
    }
   }

   maxdp[s][e] = maxV;
   mindp[s][e] = minV;
  }
 }

 cout << max(mindp[0][n - 1], maxdp[0][n - 1]);
}

댓글

댓글 쓰기

이 블로그의 인기 게시물

HTML - input file 버튼 꾸미기

-
이미지
 이번 글에선 HTML 에서 기본적으로 제공하는 input 태그의 file 속성일 때의 모양을 바꿔보려고 한다. 열심히 구글링을 해본 결과 보안상의 문제로 직접 input 태그에 변경을 가할 수는 없다고 한다. 따라서 input 태그에 속성을 넣는 게 아닌 약간의 편법?을 이용해서 업로드 버튼처럼 보이게 만들어야 한다. 먼저, 파일의 이름을 출력할 가짜 input 태그를 넣자. <input type= "text" id= "file_route" disabled= "disabled" value= "파일 선택" > value 에 안내 문구를 넣었고, disabled를 지정했기 때문에 커서를 옮겨도 아무 것도 할 수 없다. 잘 생성됐다. 이제 오른쪽 버튼과 "선택된 파일 없음" 문구를 없애고 새 버튼을 만들어야 하는데 label과 style 속성을 잘 활용해서 없애보자. <input type= "text" id= "file_route" disabled= "disabled" value= "파일 선택" > <label for= "upload_file" style= "border: solid 1px black;" > 업로드 </label> <input type= "file" id= "upload_file" accept= "image/*" required= true style= "position:absolute; clip:rect(0, 0, 0, 0);" > label 태그는 for 속성으로 연결한 id의 태그와 자신(라벨)을 연결해 준다. 즉, "업로드" 를 클릭해도 input 태그를 클릭한 것...
자세한 내용 보기

HTML - 이미지 미리보기(jQuery 없이)

-
이미지
 최근에 웹 클론 코딩을 하면서 이미지 미리보기 기능을 구현해야 됐는데 구글링해서 나온 대부분이 제이쿼리를  이용한 코드여서 찾는데 애를 좀 먹었다. 이 글에선 제이쿼리를 쓰지 않고 이미지 미리보기를 구현해보려고 한다. 먼저, 기본으로 제공되는 input 태그와 미리보기를 하기 전 기본 이미지를 띄워보자. <img src= "고양이.jpg" id= "img_section" style= "width: 400px; height: 400px;" > <br> <input type= "file" id= "upload_file" accept= "image/*" required= true value= "업로드" > src 는 본인이 원하는 기본 이미지 경로로 설정해주면 된다. (어차피 나중에 src 속성을 바꿔서 이미지가 변경됨!) id , style 등등 나머지 속성을 지정해주자. 아직은 이미지와 input 버튼만 만들었기 때문에 파일을 아무리 업로드해도 아무 변화가 없다. 이제 동적으로 img 태그의 src 를 바꿔주는 스크립트를 작성해보자. <img src= "고양이.jpg" id= "img_section" style= "width: 400px; height: 400px;" > <br> <input type= "file" id= "upload_file" accept= "image/*" required= true value= "업로드" > <script> const reader = new FileReader(); reader.o...
자세한 내용 보기

BOJ - DNA 유사도(2612)

-
문제(링크) LCS 알고리즘 응용문제입니다. dp[i][j] = i, j 지점에서 나올 수 있는 최대 유사도 공백을 추가할 때, 현재 유사도가 음수가 되버리면 그 지점부터 다시 시작하는게 이득입니다. 따라서 lcs 알고리즘과 비슷하게 문자가 같지 않다면 왼쪽, 왼쪽 위, 위 값의 최댓값을 현재 값으로 가져오는데 해당 값에 공백을 추가한 값, 즉, -2 를 한 값을 가져오고 최종 값이 음수가 되면 0으로 바꿔줘야 합니다. 문자가 같다면 lcs 알고리즘에서 처럼 +3을 해줍니다. dp 배열을 완성했다면 유사도가 최대인 점을 찾습니다. 최대인 점으로부터 가로, 세로, 대각선을 체크하면서 시작 점을 찾아가는데, 가로, 세로는 +2 , 대각선은 -3 으로 찾아가면서 0이 될때까지 찾아가고, 역으로 시작점부터 끝점까지 출력하면 됩니다. #include<iostream> #include<algorithm> #include<math.h> #include<string> #include<vector> #include<stack> #include<queue> #include<map> using namespace std; #define FIO ios_base::sync_with_stdio(false); cin.tie(NULL) #define pii pair<int, int> #define pdd pair<double, double> #define pic pair<int, char> #define ll long long #define vi vector<int> #define vl vector<long long> #define vc vector<char> #define vii vector<pii> #define IMAX 2000000001 #define LM...
자세한 내용 보기