풀이

  1. 만들 수 있는 각도로 새로운 각도를 만들어 set에 넣는다.
  2. set에 있는 원소를 vector에 넣은 다음 2중 for문을 통해 만들 수 있는 모든 각도를 만든 후 다시 set에 넣는다.
  3. 반복하다가 set의 크기와 vector의 크기가 같아지면 더 이상 추가될 게 없다는 것이므로 이 때 set에 현우가 외친 각이 있으면 YES, 없으면 NO

코드

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int n, k;
vector<int> angle;
vector<int> output;
void input() {
  cin >> n >> k;
  int temp;
  for(int i=0;i<n;++i) {
    cin >> temp;
    angle.push_back(temp);
  }
  for(int i=0;i<k;++i) {
    cin >> temp;
    output.push_back(temp);
  }
}

int convert(int num) {
  if(num >= 360) {
    return num - 360;
  }
  if(num < 0) {
    return num + 360;
  }
  return num;
}

set<int> ans;
void process() {
  int nowAnsLength = 0; 
  for(int i=0;i<angle.size(); ++i) {
    ans.insert(convert(angle[i]));
  }
  for(int i=0;i<angle.size(); ++i) {
    for(int j=0;j<angle.size(); ++j) {
      ans.insert(convert(angle[i] + angle[j]));
      ans.insert(convert(angle[i] - angle[j]));
    }
  }
  while(nowAnsLength != ans.size()) {
    nowAnsLength = ans.size();
    vector<int> temp_vec;
    for(auto x : ans) {
      temp_vec.push_back(x);
    }
    for(int i=0;i<temp_vec.size(); ++i) {
      for(int j=0;j<temp_vec.size(); ++j) {
        ans.insert(convert(temp_vec[i] + temp_vec[j]));
        ans.insert(convert(temp_vec[i] - temp_vec[j]));
      }
    }
  }
  for(int i=0;i<output.size();++i) {
    if(ans.count(output[i]) == 0) {
      cout << "NO" << endl;
    } else {
      cout << "YES" << endl;
    }
  }
  return;
}

int main(void) {
  input();
  process();
}

'알고리즘' 카테고리의 다른 글

Codility - MinAbsSumOfTwo  (0) 2020.12.30
백준 4902 삼각형의 값 c++  (0) 2020.09.17
백준 2210 숫자판 점프 c++  (0) 2020.09.15
백준 2933 미네랄 C++ 풀이  (0) 2020.09.12
백준 2776 CPP, js  (0) 2020.09.04

풀이

모든 경우의 수를 다 해보면 되는 문제.

코드

#include <iostream>
#include <set>
#include <vector>

using namespace std;

char table[5][5];
set<string> s;

void input() {
  for(int i=0;i<5;++i) {
    for(int j=0;j<5;++j) {
      cin >> table[i][j];
    }
  }
}

bool rangeCheck(int nx, int ny) {
  return 0 <= nx && nx < 5 && 0 <= ny && ny < 5;
}

vector<char> temp;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void dfs(int y, int x) {
  if(temp.size() == 6) {
    string make = "";
    for(int i=0;i<temp.size(); ++i) {
      make += temp[i];
    }
    s.insert(make);
    return;
  }

  for(int k=0;k<4;++k) {
    int nx = x + dx[k];
    int ny = y + dy[k];
    if(rangeCheck(nx, ny)) {
      temp.push_back(table[ny][nx]);
      dfs(ny, nx);
      temp.pop_back();
    }
  }
}

void processing() {
  for(int i=0;i<5;++i) {
    for(int j=0;j<5;++j) {
      temp.push_back(table[i][j]);
      dfs(i, j);
      temp.pop_back();
    }
  }

  cout << s.size();
}

int main() {
  input();
  processing();
}

'알고리즘' 카테고리의 다른 글

백준 4902 삼각형의 값 c++  (0) 2020.09.17
백준 2916 자와 각도기 c++  (0) 2020.09.15
백준 2933 미네랄 C++ 풀이  (0) 2020.09.12
백준 2776 CPP, js  (0) 2020.09.04
[javascript] b1072.js  (0) 2020.09.03

문제 링크

풀이

eraseBlock();
rootedClusterCheck();
flyClusterDown();

eraseBlock();

왼쪽, 오른쪽에서 막대기를 던질 때 해당하는 block을 제거하는 로직.

 

rootedClusterCheck();

rooted → 땅에 박혀있는 이라는 의미로 변수명 지었다. 땅(row == 0) 까지 연결되어 있는 클러스터는 땅으로 떨어지지 않기 때문에 먼저 땅과 연결되어 있는 클러스터들을 체크해줬다.

체크한 방법은 row == 0에 있는 것 중에서 x가 있으면 그걸 시작점으로 dfs를 돌면서 연결되어 있는 것들을 체크했다.

 

flyClusterDown();

앞에서 땅과 연결되어 있는 클러스터들은 체크가 됐다. 그렇다면 입력 테이블에서 'x'이면서 땅과 연결된 클러스터로 체크되지 않은 것은 모두 공중에 있는 클러스터일 것이다. 문제조건에 두 개 이상의 클러스터는 공중에 있지 않다고 했으므로 해당하는 x를 만나면 거기서 dfs를 통해 공중에 있는 클러스터들을 체크해줬다.

그리고 이 클러스터를 땅이나 만나는 미네랄에 연결시켜줘야 한다. 이 클러스터는 전체적으로 똑같은 col만큼 아래로 하강하는데 이 값을 효율적으로 구하기 위해 dfs돌면서 각 column의 가장 작은 row값을 따로 저장해 뒀다.

int findDownLength() {
  int minLength = 9999999;
  for(int j=0;j<c;++j) {
    if(columnList[j] == 999999) continue;
    for(int i=0;i<r;++i) {
      if(table[i][j] == 'x') {
        if(i == columnList[j]) {
          minLength = min(minLength, i);
          break;
        } else {
          minLength = min(columnList[j] - i - 1, minLength);
        }
      }
    }
  }
  return minLength;
}

이 값들은 위와 같은 코드에 사용되는데 땅부터 row를 증가시키면서 찾다가 테이블에 'x'를 만났다면 두 가지 경우중 하나이다.

첫 번째는 공중에 떠있는 자기자신을 만났을 때,

두 번째는 다른 땅과 연결된 클러스터를 만났을 때이다.

전자는 자기를 만났기 때문에 자기 위쪽은 탐색할 필요 없다. 그래서 클러스터를 몇칸 땅으로 이동시킬지에 대한 변수인 minLength를 자기 row값으로 min(minLength, i)로 최신화 시켜주었다.

후자는 지금 만난 x보다 더 위에도 x가 존재할 수 있고, 그 때에는 minLength가 더 작아지기 때문에 추가적인 탐색이 필요해 break를 걸지 않았다.

이렇게 몇칸 아래로 내릴지 구한다음 공중에 떠있는 클러스터들은 모두 체크가 되어 있기 때문에 그 칸만큼 내려준다.

이 3가지 과정을 N번 진행하면 문제가 풀린다.

코드

#include <iostream>
#include <vector>

using namespace std;

char table[101][101];

int r, c;
bool isrootedCluster[101][101];
void rootedClusterClear() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      isrootedCluster[i][j] = false;
    }
  }
}

vector<int> stickThrowRow;

void input() {
  cin >> r >> c;
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      cin >> table[r-i-1][j];
    }
  }
  int n;
  cin >> n;
  int temp;
  for(int i=0;i<n;++i) {
    cin >> temp;
    stickThrowRow.push_back(temp); 
  }
}

bool blockErase(int row, int col) {
  if(table[row][col] == 'x') {
    table[row][col] = '.';
    return true;
  }
  return false;
}

void eraseBlock(int throwIdx, bool isRightToLeft) {
  if(isRightToLeft) {
    for(int i=0;i<c;++i) {
      if(blockErase(throwIdx, i)) return;
    }
  } else {
    for(int i=c-1;i>=0;--i) {
      if(blockErase(throwIdx, i)) return;
    }
  }
}

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool dfsRangeChk(int nx, int ny) {
  return (0 <= nx && nx < c && 0 <= ny && ny < r);
}

bool dfsVisited[101][101];
void dfsVisitedClear() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      dfsVisited[i][j] = false;
    }
  }
}

bool columnCheckNeeded = false;
int columnList[101];
void clearColumnList() {
  for(int i=0;i<101;++i) {
    columnList[i] = 999999;
  }
}

void dfs(int row, int col) {
  for(int i=0;i<4;++i) {
    int nx = col + dx[i];
    int ny = row + dy[i];
    if(dfsVisited[ny][nx] == false && dfsRangeChk(nx, ny)) {
      if(table[ny][nx] == 'x'){
        if(columnCheckNeeded) {
          columnList[nx] = min(columnList[nx], ny);
        }
        dfsVisited[ny][nx] = true;
        dfs(ny, nx);
      }
    }
  }
}

void pasteRootedResult() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      if(dfsVisited[i][j] == true) {
        isrootedCluster[i][j] = true;
      }
    }
  }
}

void rootedClusterCheck() {
  for(int i=0;i<c;++i) {
    if(isrootedCluster[0][i] == false && table[0][i] == 'x') {
      dfsVisitedClear();
      isrootedCluster[0][i] = true;
      dfs(0, i);
      pasteRootedResult();
    } 
  }
}

void findflyCluster(int i, int j) {
  dfsVisitedClear();
  dfsVisited[i][j] = true;
  columnList[j] = i;
  dfs(i, j);
}

int findDownLength() {
  int minLength = 9999999;
  for(int j=0;j<c;++j) {
    if(columnList[j] == 999999) continue;
    for(int i=0;i<r;++i) {
      if(table[i][j] == 'x') {
        if(i == columnList[j]) {
          minLength = min(minLength, i);
          break;
        } else {
          minLength = min(columnList[j] - i - 1, minLength);
        }
      }
    }
  }
  return minLength;
}

void downCluster() {
  int downLength = findDownLength();
  for (int j = 0; j < c; ++j) {
    for (int i = 0; i < r; ++i) {
      if(dfsVisited[i][j] == true) {
        table[i][j] = '.';
        table[i-downLength][j] = 'x';
      }
    }
  }
}

void flyClusterDown() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j){
      if(isrootedCluster[i][j] == false && table[i][j] == 'x') {
        clearColumnList();
        columnCheckNeeded = true;
        findflyCluster(i, j);
        columnCheckNeeded = false;
        downCluster();
        return;
      }
    }
  }
}

void processing() {
  for(int i=0;i<stickThrowRow.size(); ++i) {
    eraseBlock(stickThrowRow[i]-1, i%2==0);
    rootedClusterCheck();
    flyClusterDown();
    rootedClusterClear();
  }
}

void printAnswer() {
  for(int i=0;i<r;++i) {
    for(int j=0;j<c;++j) {
      cout << table[r-i-1][j];
    }
    cout << '\n';
  }
}

int main(void) {
  // freopen("b2933.txt", "r", stdin);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  processing();
  printAnswer();
}

'알고리즘' 카테고리의 다른 글

백준 2916 자와 각도기 c++  (0) 2020.09.15
백준 2210 숫자판 점프 c++  (0) 2020.09.15
백준 2776 CPP, js  (0) 2020.09.04
[javascript] b1072.js  (0) 2020.09.03
[프로그래머스] 정수삼각형 c++ 재귀로 풀기  (0) 2020.07.04

A. Ahahahahahahahaha

n / 2 이하로만 뽑으면 됐다. 0과 1밖에 안나오기 때문에 0이 n / 2 이상 개수가 있었으면 n / 2개만큼의 0을 출력해주면 되고 0이 n / 2 미만이었다면 1이 n / 2 + 1 개 있다는 것이므로 1을 n / 2 + 1 만큼 출력하면 되는 문제였다.

B. Big Vova

안그래도 영어라 읽기 힘든데 무려 한 문단이 문제와 관련없었다. 맨 앞에 오는 숫자는 반드시 a 배열중에서 가장 큰 숫자여야 했다. GCD(b1)에서 그 수 자체가 c1이 되는데 사전순으로 가장 크게 될려면 가장 큰 숫자가 왔어야 하기 때문이다.

처음에 풀면서 n^2에 gcd까지 구하는 풀이가 생각났는데 n제한이 10^5인줄 알고 이 방법을 쓰지 않고 다른 걸 찾다가 시간을 많이 썼다. 10^3인걸 잘 봤으면 이렇게 풀고 빨리 끝냈을 수 있을 것 같다.

C. Chocolate Bunny

크기가 다른 두 숫자를 순서 바꿔서 한번 씩 mod연산 하면 둘 중 작은 값이 두 숫자 중 작은 값이다. 이를 이용해서 풀 수 있었다.

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
// const input = require('fs').readFileSync('./input.txt').toString().split('\n');

let a = [];
let b = [];
let z;
const bs = (left, right) => {
  const mid = Math.floor((left + right) / 2); 
  if(left > right) {
    return 0;
  }
  let tval = a[mid]; 
  if(tval > z) {
    return bs(left, mid-1);
  } else if(tval < z){
    return bs(mid+1, right);
  } else {
    return 1;
  }
}

for(let i=0;i<Number(input[0]);++i) {
  a = input[i*4+2].split(' ').map(x => parseInt(x));
  b = input[i*4+4].split(' ').map(x => parseInt(x));
  a.sort();
  for(const v of b) {
    z = v;
    console.log(bs(0, Number(input[i*4+1]-1)));
  }
}
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int arr[1000010];
int cmp;
int bs(int left, int right) {
  int mid = (left + right) / 2;
  if(left > right) {
    return 0;
  }
  int tval = arr[mid];
  if(tval > cmp) {
    return bs(left, mid-1);
  } else if(tval < cmp) {
    return bs(mid+1, right);
  } else {
    return 1;
  }
}

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

  cin >> t;
  while(t--) {
    int a, b;
    cin >> a;
    for(int i=0;i<a;++i) {
      cin >> arr[i];
    }
    sort(arr,arr+a);
    cin >> b;
    for(int i=0;i<b;++i) {
      cin >> cmp;
      cout << bs(0,a-1) << '\n';
    }
  }
}

js로 똑같이 구현해도 시간초과가 났다. 질의응답에서 데이터 입력이 많아 입력속도가 중요하다고 하는데 javascript로 어떻게 올려야 할지 모르겠다.

'알고리즘' 카테고리의 다른 글

백준 2210 숫자판 점프 c++  (0) 2020.09.15
백준 2933 미네랄 C++ 풀이  (0) 2020.09.12
[javascript] b1072.js  (0) 2020.09.03
[프로그래머스] 정수삼각형 c++ 재귀로 풀기  (0) 2020.07.04
[DC] 백준 1992 쿼드트리  (0) 2018.04.29
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
// const input = require('fs').readFileSync('./input.txt').toString().split('\n');

const bs = (left, right, z) => {
  const mid = Math.floor((left + right) / 2); 
  if(left >= right) {
    return mid;
  }
  let tval = Math.floor(((Y + mid) / (X + mid))* 100);
  if(tval > z) {
    return bs(left, mid, z);
  } else {
    return bs(mid+1, right, z);
  }
}

let a = input[0].split(' ');
const X = Number(a[0]);
const Y = Number(a[1]);
const Z = Math.floor((100 * Y / X));
let result = 0;
result = bs(0, 100000000001, Z);
if(result == 100000000001) {
  result = -1;
}
console.log(result);

풀이

Lower bound 알고리즘으로 풀 수 있었다.이분 탐색이랑 유사하지만 조건 만족할 때에는 mid를 증가시키지 말고 만족 안할 때 mid를 증가시켜 탈출 조건에서 조건 만족시켰던 것 중 가장 먼저 나오는 답을 return 한다.

문제였던 것

// 입력 X = 50, Y = 29 일때
console.log(100 * Y / X);
console.log(Y / X * 100)

//output
58
57.999999999...

위와 같이 차이가 있었다.

'알고리즘' 카테고리의 다른 글

백준 2933 미네랄 C++ 풀이  (0) 2020.09.12
백준 2776 CPP, js  (0) 2020.09.04
[프로그래머스] 정수삼각형 c++ 재귀로 풀기  (0) 2020.07.04
[DC] 백준 1992 쿼드트리  (0) 2018.04.29
[DC] 백준 1074 Z  (0) 2018.04.29

B. Power Sequence

https://codeforces.com/contest/1397/problem/B

처음에 너무 난해했다. 모든 경우를 다 하지 않고 어떻게 구할 수 있는지 고민을 많이 했다. 고민을 하던 중에 c가 2만 되더라도 n이 10^5는 고사하고 n이 30만 되도 10^9를 넘어 사실상 c가 1일때만 10^5만큼 해봐야하고 그 이상일 땐 정말 적은 양만 탐색해보면 되는 문제였다.

C. Multiples of Length

https://codeforces.com/contest/1397/problem/C

어떻게 풀어야 할지 감이 안왔다. 정렬 후 세그먼트 트리로 풀 수 있을까 생각해봤는데 그렇게 하더라도 경우의 수가 너무 많았다. 도저히 생각이 안나서 다른사람 코드를 봤는데 너무 간단해서 허무했다. 1~n-1까지 각 값에 n-1을 곱해 더하면 arr[i] * (n-1) + arr[i] 하면 1~n-1까지의 값이 모두 arr[i] * n 이 되고 n~n까지는 구간의 길이가 1이라 무엇이든 곱해도 되니 arr[last] * (n-1) + arr[last] 로 arr[last] * n 을 만든다. 마지막으로 1~n까지에 -1 * arr[i] * n으로 더해주면 모두 0을 만들 수 있었다. 코드포스식 쉬운 문제들은 이런식의 접근을 해야겠다는 생각을 했다.

D. Stoned Game

https://codeforces.com/contest/1397/problem/D

그리디인건 알겠는데 또 감이 안왔다. 백준에 많은 돌 게임 문제가 있었는데 이건 좀 유형이 다르고 DP로 풀 수 있는 문제였다. 다른 사람의 풀이를 보고 감을 잡고 풀 수 있었다. 먼저 가장 간단하게 생각하면 돌 개수 총 합이 홀수개면 T가 이기고 짝수면 HL이 이긴다. 여기서 변수는 T나 HL이 뽑은 게 마지막 남은 pile이어서 돌이 남았더라도 뽑을 수 없게 되면 돌의 개수와 상관없이 그 돌을 점유하고 있던 플레이어가 이긴다. 이러한 상황은 T만 만들 수 있다. 이 상황이 나오려면 가장 큰 pile이 나머지 pile의 모든 합보다 크면 T가 그 pile만 계속 점유하면 이기기 때문에 이 경우를 예외처리하고 이외에는 짝수홀수 경우로 답을 구했다.

 

#include <string>
#include <vector>

using namespace std;

int dp[510][510];
vector<vector<int> > *arr;

void init() {
    for(int i=0;i<510;++i) {
        for(int j=0;j<510;++j) {
            dp[i][j] = 0;
        }
    }
}

int dfs(int depth, int idx) {
    if(depth == arr->size()) {
        return 0;
    }    
    if(dp[depth][idx] != 0) {
        return dp[depth][idx];
    }
    
    dp[depth][idx] = max((*arr)[depth][idx] + dfs(depth + 1, idx), 
    			(*arr)[depth][idx] + dfs(depth + 1, idx + 1));    
 
   
    return dp[depth][idx];
}

int solution(vector<vector<int>> triangle) {
    arr = &triangle;
    init();
    int answer = 0;
    answer = dfs(0,0);
    return answer;
}

'알고리즘' 카테고리의 다른 글

백준 2776 CPP, js  (0) 2020.09.04
[javascript] b1072.js  (0) 2020.09.03
[DC] 백준 1992 쿼드트리  (0) 2018.04.29
[DC] 백준 1074 Z  (0) 2018.04.29
[DC] 백준 2261 가장 가까운 두 점  (0) 2018.04.29

A. Minimum Binary Number



처음 문제를 봤을 때 operation을 1번이나 제한적으로 쓸 수 있다고 생각해서 A 부터 엄청 어려운 게 나왔구나 했는데 계속 사용이 가능했다. 보면 나올 수 있는 최소의 값은 0의 개수를 세어주고 그 뒤에 1을 붙이거나, input이 1 0 인 예외를 처리해주면 통과되었다. 

#include <iostream>
#include <string>
using namespace std;
char arr[1001];
int main(void) {
       int n;
       cin >> n;
       string s;
       cin >> s;
       if (n == 1 && s[0] == '0') {
               cout << '0' << endl;
               return 0;
       }
       int cnt = 0;
       for (int i = 0; i < n; ++i) {
               if (s[i] == '0') {
                      cnt++;
               }
       }
       cout << '1';
       for (int i = 0; i < cnt; ++i) {
               cout << '0';
       }
       return 0;
}



B. Lara Croft and the New Game


처음 문제를 봤을 때 x좌표와 y좌표를 k,n,m에 대해서 나타낼 수 있을 걸 알았지만 교육적인 목적에서 직접 경로를 탐색하는 코드를 짜보았다. 무슨 생각인 진 모르겠지만 k가 10^9보다 작다고 생각해서 시간초과는 안 날 것이라 생각했는데 짜놓고 제출하고 시간초과가 나서 생각해보니 최악의 경우 INT32_MAX-1까지 가능했다. 20억번이므로 대략 20초가 걸리므로 당연히 시간초과
그래도 구현한 코드를 올려보면 

#include <iostream>
#include <string>
using namespace std;
int c;
int x = 1, y = 1;
bool inturrupt() {
       if (x == 1 && y == 2) {
               cout << x << ' ' << y << endl;
               return 1;
       }
       if (c == 0) {
               cout << x << ' ' << y << endl;
               return 1;
       }
       c--;
       return false;
};
void print() {
       cout << x << ' ' << y << endl;
}
int main(void) {
       int a, b;
       cin >> a >> b >> c;
       a--;
       b--;
       //print();
       if (inturrupt()) {
               return 0;
       }
       
       for (int i = 1; i <= a; ++i) {
               x++;
               if (inturrupt()) {
                      return 0;
               }
               //print();
       }
       for (int i = 1; i <= b; ++i) {
               y++;
               if (inturrupt()) {
                      return 0;
               }
               //print();
       }
       while (c != 0) {
               x--;
               if (inturrupt()) {
                      return 0;
               }
//print();
               for (int i = 1; i <= b - 1; ++i) {
                      y--;
                      if (inturrupt()) {
                              return 0;
                      }
               //     print();
               }
               x--;
               if (inturrupt()) {
                      return 0;
               }
               //print();
               for (int i = 1; i <= b - 1; ++i) {
                      y++;
                      if (inturrupt()) {
                              return 0;
                      }
               //     print();
               }
       }
       return 0;
}

inturrupt 함수는 한번 x나 y를 바꾸는 연산을 한 다음에 실행시켜 줘서 k가 0이 되면 x,y를 출력하고 끝내도록 만들었다. 코드는 엄청 복잡했다. 

#include <iostream>
#include <string>
using namespace std;
int c;
int x = 1, y = 1;
int main(void) {
       int n, m;
       cin >> n >> m >> c;
       if (c < n) {
               cout << 1 + c << ' ' << 1 << endl;
               return 0;
       }
       if (c < n + m - 1) {
               cout << n << ' ' << (c - (n - 1)) + 1 << endl;
               return 0;
       }
       if (n*m - 1 == c) {
               cout << 1 << ' ' << 2 << endl;
               return 0;
       }
       c -= (m + n - 2);
       int temp = n - 1 - ((c-1) / (m - 1));
       int temp2;
       if (temp % 2 == 0) {
               temp2 = 1 + (c-1) % (m - 1);
       }
       else {
               temp2 =  m - 1 - (c-1) % (m - 1);
       }
       cout << temp << ' ' << temp2 + 1 << endl;
       return 0;
}

x와 y를 n,m,k에 대한 식으로 나타내서 짠 코드. 여기서 
Note that k doesn't fit into 32-bit integer type!
이런 문구가 있는 걸 간과했다. long long 으로 작성하면 accept를 받을 수 있었다. 



C. Nested Segments


뻔한 문제 같은데 도저히 풀 방법이 생각나지 않았다. Contest 가 끝나고 나서 코드를 확인해 보니

좌표를 묶어서 first 크기대로 정렬을 한다. first가 같으면 second가 작은 순으로 정렬한다. 

본래 순서의 index를 가지고 있어야 하므로 index배열을 따로 만들고 index배열을 정렬시키면서 정럴시키는 cmp 함수안의 조건은 pair값을 사용한다. 

정렬이 끝나면 첫번째 값은 무조건 다음값에 포함되므로 생각하지 않고 second 값만 비교한다. 

#include <iostream>
#include <algorithm>
using namespace std;
int u[300001];
pair<int, int> in[300001];
int main(void)
{
       int n;
       cin >> n;
       for (int i = 1; i <= n; ++i) {
               u[i] = i;
               cin >> in[i].first >> in[i].second;
       }
       sort(u + 1, u + n + 1, [](int a, int b) {
               if (in[a].first != in[b].first) {
                      return in[a].first < in[b].first;
               }
               else {
                      return in[a].second > in[b].second;
               }
       });
       int temp = u[1];
       for (int i = 2; i <= n; ++i) {
               if (in[temp].second >= in[u[i]].second) {
                      cout << u[i] << ' ' << temp << endl;
                      return 0;
               }
               else {
                      temp = u[i];
               }
       }
       cout << -1 << ' ' << -1 << endl;
       return 0;
}




A. Splits

A 번 문제가 아니었다면 못풀었을 것 같다. 
A라 분명 쉬울껀데 하면서 계속 해보니까 
결국 중요한 건 맨 앞에 오는 숫자의 개수이고 뒤는 1로 다 채워버려도 됐다. 
어떤 숫자가 n이라면

n개를 다 1로 채우는 방법,
n개에서 한개를 2로하고 나머지를 1로 채우는 방법
n개에서 2개를 2로하고 나머지를 1로 채우는 방법

... 

n개에서 n/2개를 2로하고 나머지가 있다면 1로 두는 방법 으로 구할 수 있다.

따라서 모든 방법의 수는 n/2+1

#include <iostream>
using namespace std;
int main(void)
{
       int n;
       cin >> n;
       cout << n / 2 + 1;
       return 0;
}



B. Messages


브루트포스로 풀었다. 

편지를 안 읽고 두냐, 아니면 얼른 읽어버리냐의 최대값의 차이는 

(t-ti)*c + (a-b*(t-ti))

이런 수식으로 구할 수 있었다. ti를 편지를 받은 tb[i] 부터 끝까지 가지고 있는 <= t 로 범위를 준 후 다 해본다음의 max 값을 ans 에 더해줘서 구했다. 

이게 될까 싶었는데 돌려보니 바로 Accept 가 떠서 신기했다. 

#include <iostream>
#include <algorithm>
using namespace std;
int tb1[100001];
int main(void)
{
       int n, a, b, c, t;
       cin >> n >> a >> b >> c >> t;
       for (int i = 0; i<n; ++i) {
              cin >> tb1[i];
       }
       int ans = 0;
       for (int i = 0; i<n; ++i) {
              int tmax = 0;
              for (int ti = tb1[i]; ti <= t; ++ti) {
                     int temp = (t - ti)*c + (a - b * (t - ti));
                     tmax = max(tmax, temp);
              }
              ans += tmax;
       }
       cout << ans << endl;
       return 0;
}






+ Recent posts