본문 바로가기

분류 전체보기

 (224)
백준 11000 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si > n; for (int i = 0; i > s >> e; cls.push_back({s,..
백준 17836 공주님을 구해라! https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net #include #include #define INF 987654321 using namespace std; //0: 길, 1: 벽, 2: 칼 int map[101][101]; int cost[101][101]; bool isVisit[101][101]; int ny[4] = {-1, 1, 0, 0}; int nx[4] = {0, 0, -1, 1}; int main() { ios:..
백준 15486 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net #include #include #include #define MAX_NUM 1500001 using namespace std; //dp[i]: i일에 받을 수 있는 최대 이익 int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int ans = 0; cin >> n; vect..
백준 2448 별 찍기 (11) divide & conquer #include #define MAX_SIZE 3072 //3*pow(2, 10) using namespace std; char star[MAX_SIZE][MAX_SIZE * 2]; //가장 윗 꼭짓점의 좌표(r,c), 별의 크기 n void makeStar(int r, int c, int n) { //deg case if (n == 3) { //ㅁㅁ*ㅁㅁㅁ star[r][c] = '*'; //ㅁ*ㅁ*ㅁㅁ star[r + 1][c - 1] = '*'; star[r + 1][c + 1] = '*'; //*****ㅁ star[r + 2][c - 2] = '*'; star[r + 2][c - 1] = '*'; star[r + 2][c] = '*'; star[r + 2][c + 1..
백준 21314 민겸 수 https://www.acmicpc.net/problem/21314 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); string s; cin >> s; vector ans; //최댓값 연산 int mcnt = 0; int kcnt = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == 'M') { mcnt++; } else if (s[i] == 'K') { kcnt++; } if (kcnt != 0) { ans.push_back('5'); for (int j = 0; j < mcnt; j++) { ans.push_..
백준 16953 A → B 큐에 b보다 작은 연산결과들을 연산의 횟수와 같이 집어넣고 연산으로 b를 만들었다면 그 횟수를 출력하는 방식으로 구현하였다. #include #include #define INF 987654321 using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long a, b; cin >> a >> b; queue q; //first: 해당 숫자, second: 연산의 수에 1을 더한 것 q.push({a, 1}); while (!q.empty()) { long long cur = q.front().first; int cnt = q.front().second; q.pop(); if (cur ..
백준 19637 IF문 좀 대신 써줘 https://www.acmicpc.net/problem/19637 문제에서의 if문을 그대로 사용하게 되면 시간초과가 발생한다. 이를 개선하기 위해 binary search 알고리즘을 사용하여 해결했다. 입력된 power가 들어오면 이게 어느 경계 전투력에 포함되는지 확인한다. 그 후 mid의 칭호를 쓸지 다음의 칭호를 쓸지 확인한다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; vector grade(n); for (int i = 0; i > grade[i]..
백준 17352 여러분의 다리가 되어 드리겠습니다! https://www.acmicpc.net/problem/17352 전형적인 분리집합 문제이다. 주어진 edge의 vertex를 모두 union하게 되면 입력 조건에 의해 단 한개의 구간만 parent가 다르게 나온다. 이를 나머지 vertex 중 아무 것과 잇게되면 어떤 두 섬 사이든 왕복할 수 있게 된다. #include #include using namespace std; int parent[300001]; int findParent(int k){ if (parent[k] == k) { return k; } return parent[k] = findParent(parent[k]); } void merge(int a, int b){ if (findParent(a) == findParent(b)) { ..

티스토리툴바