문제풀이

[C++] 백준 7662번 문제풀이

이 문제를 보고 queue 를 2개 사용해서 풀려고 했는데 쉽지 않았다. 오름차순과 내림차순 2개의 queue 를 사용하려고 했으나 오름차순에서 마지막 수가 내림차순의 첫 번째 수를 넘게 되면 머리가 어지러워 진다. 자료조사를 하던중 set을 알게되어 set 을 사용하여 풀었다. multi set 과 set 의 차이점은 key 값이 중복이 된다는 점이 였다. set을 알면 쉽게 풀 수 있는 문제였다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); int cnt; cin >> cnt; while (cnt--) { int a; cin >> a..

[C++] 백준 20546번 문제풀이

이 문제는 풀때 딱히 어려운 개념은 없었다. 한가지 헷갈렸던 점은 C++은 수학이랑 다르단 점 (A/B)*B = A 가 아니란 점만 알고 넘어가자 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int arr[14]; int cash; cin >> cash; int JH = cash;//준현이가 가지고 있는 현금 int JHnum=0;//준현이가 가지고 있는 주 개수 int SM = cash;//성민이가 가지고 있는 현금 int SMnum = 0;//성민이가 가지고 있는 주 개수 for (int i = 0; i > num; arr[i..

[C++] 백준 20544 문제풀이

이 문제를 보고 DP 를 사용해야 되겠다고 생각하였다. DP 문제를 많이 다루지 못해서 이 문제는 충분히 생각한 뒤 다른 사람의 풀이를 참조 하여 코드를 해석하고 왜 이런 코드를 썼는지 이해하였다. 다음 문제를 풀땐 내가 직접 풀어보자 ... 우선 코드를 해석하였을 때 체크 해야 할것들이 여러가지가 있는데 첫 번째 도현이의 위치 두 번째 과거 허들 높이 세 번째 현재 허들 높이 네 번째 허들의 높이가 2이상인 경우가 있는가 ? 이 4개를 고려하여 동적 프로그래밍을 해야한다. #include #include #include using namespace std; long long dp[1001][3][3][2]; long long mod = 1000000007; int N; long long solve(in..

[C++] 백준 7576번 문제풀이

이 문제를 보고 2차원 하루 지났을 때 토마토가 어떻게 퍼지는지 보았는데 입력이 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 일 때 . Day 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 Day 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 Day 3 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 이런식으로 BFS 를 써야 될거 같이 생겼다. 좌표를 하나의 node 라고 생각하면 근처의 node 들을 방문한뒤 다음 node 의 근처 node들을 방문 하는 식이다. BFS 를 좌표로 표현하기 위해 pair 를 사용하여 x축 , y축을..

[C++] 백준 2630 문제풀이

문제를 보고 든 생각은 사각형을 사분면으로 생각해서 풀어야겠다고 생각했다. 사분면을 검사할때 사분면의 원소가 사분면의 제일 왼쪽 위에 있는 원소와 다르다면 , 사분면을 잘라서 다시 검사하게 만들었다. bool check 를 쓴 이유는 사분면 검사를 통과했는지 유무를 검사하기 위해 사용하였다. #include using namespace std; int arr[128][128]; int blue = 0; int white = 0; void cut(int n1, int n2,int N) { bool check = true; int index = arr[n1][n2]; for (int i = n1; i > num; for (int i = 0; i < num; i++) { for (int j = 0; j < n..

[C++] 백준 2606 문제풀이

벡터를 활용한 dfs 를 사용하면 쉽게 풀 수 있었다. 동적할당을 사용하여 벡터를 이용하려면 vector * a = new vector[cnt + 1]; 이런식으로 선언을 해야한다. #include #include using namespace std; bool visited[100] = { false, }; int c = 0; void dfs(vectora[],int index) { visited[index] = true; for (int i = 0; i > cnt; vector * a ..

[C++] 백준 1931 문제풀이

이 문제를 제대로 읽지 않고 풀었더니 오류가 나왔다. 최대 사용할 수 있는 회의의 최대 개수를 구해야하는데 최대 개수를 구하지 않고 개수만 구하였더니 계속 오류가 났다 이를 해결하기 위해 정렬을 해줘야 하는데 vector 에서 pair 형태로 넣고 회의가 끝나는 시간이 같다면 회의가 시작하는 시간이 더 빠른 회의를 우선으로 회의가 끝나는 시간이 다르다면 회의가 끝나는 시간이 더 빠른 회의를 우선으로 정렬하였다. #include #include #include using namespace std; vectors; bool cmp(pair first, pair second) { if (first.second == second.second) return first.first < second.first; els..

[C++] 백준 1927번 문제풀이

작년에 자료구조 수업을 들을 때 직접 heap 을 구현하였다. 이 문제도 그렇게 푸는 줄 알았는데 heap 과 관련된 자료를 검색하던중 priority_queue q; 이러한 방법을 찾게 되어 priority_queue 을 사용하여 문제를 풀었다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(0); priority_queue q; int n; cin >> n; while (n--) { int num; cin >> num; if (num == 0) { if (q.size() == 0)cout