본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 15596 정수 N개의 합 출처: https://www.acmicpc.net/problem/15596 주어진 함수 구조를 이용하는 문제로 Sample I/O가 존재하지 않는다. #include #include using namespace std; long long sum(vector &arr) { long long result = 0; for (int i = 0; i < arr.size(); i++) { result += arr[i]; } return result; } 2021. 2. 28.
[BOJ] 백준 1182 부분수열의 합 출처: https://www.acmicpc.net/problem/1182 Input 5 0 -7 -3 -2 5 8 Output 1 N이 크지 않은 숫자이므로 부분 수열의 크기를 줄여가며 모든 부분 수열의 합을 구한 후, S와 같은지 확인합니다. #include using namespace std; int N, S, result; int arr[20]; void solve(int idx, int sum){ sum += arr[idx]; if (idx >= N) return; if (sum == S) result++; solve(idx + 1, sum); solve(idx + 1, sum - arr[idx]); } int main(void) { cin >> N >> S; for(int i=0; i> arr[.. 2021. 2. 28.
[BOJ] 백준 1952 달팽이2 출처: https://www.acmicpc.net/problem/1952 Input 5 3 Output 5 시계 방향으로 방향을 바꾸므로, → ↓ ← ↑ 순서로 방향을 바꿉니다. 벽에 부딪히거나 이미 그린(방문) 곳이면 방향을 전환하면 됩니다. Q.달팽이 모양으로 표의 모든 지점을 완료한 시점은 언제일까? A. 방향을 바꿨음에도 불구하고 더 이상 그릴 수 없는 곳인 경우입니다. 즉, 방향을 바꾸고 진행할 곳이 이미 방문한 곳인 경우입니다. #include #include #include #include using namespace std; bool visited[100][100]; int dx[] = { 0, 1, 0, -1 }; int dy[] = { 1, 0, -1, 0 }; int main(void.. 2021. 2. 28.
[BOJ] 백준 11559 Puyo Puyo 출처: https://www.acmicpc.net/problem/11559 Input ...... ...... ...... ...... ...... ...... ...... ...... .Y.... .YG... RRYG.. RRYGG. Output 3 ① DFS 탐색을 통해 터질 수 있는 그룹을 찾아 폭파시킵니다. map[][]에서 각 지점별로 DFS 처리해야 합니다. ex) 아래는 총 2 그룹에서 터지지만 연쇄 횟수는 1번으로 측정됩니다. ..G.BB ..B.BB RRRRGG GGRRRR ② 폭파로 비워져 버린 공간을 채워야 합니다. 한 개의 열을 기준으로 처리. ③ 터지는 뿌요가 없어질 때까지 ①, ② 과정 반복. #include #include #include #include #include usi.. 2021. 2. 28.
[BOJ] 백준 5532 방학 숙제 출처: https://www.acmicpc.net/problem/5532 Input 20 25 30 6 8 Output 15 총 20일 중 국어숙제는 5일에 걸쳐서 완료할 수 있으며 수학숙제는 4일에 거쳐서 완료할 수 있으므로 모든 숙제를 완료하는데 걸린 기간은 5일입니다. ▶ 20 - 5 = 15 ① 국어와 수학 숙제를 모두 완료하는 기간 중 최대값을 구합니다. ② 방학기간 - 숙제 완료 기간을 통해 놀 수 있는 기간을 구합니다. #include using namespace std; int maxOfValue(int x, int y){ if(x > y) return x; else return y; } int findElapsedTime(int totalPage, int perPage){ int elap.. 2021. 2. 28.
[BOJ] 백준 2979 트럭 주차 출처: https://www.acmicpc.net/problem/2979 Input 5 3 1 1 6 3 5 2 8 Output 33 truckCnt[101];에 분 단위로 주차된 트럭의 개수를 구한 후, 주차된 개수에 맞게 요금을 측정합니다. #include using namespace std; int truckCnt[101]; int main() { int A, B, C; cin >> A >> B >> C; for (int i = 0; i > s >> e; // 각 시간대별 주차한 트럭 개수 for (int j = s; j < e; j++) { truckCnt[j]++; } } int result = 0; for (int i = 1; i 2021. 2. 28.
[BOJ] 백준 1018 체스판 다시 칠하기 출처: https://www.acmicpc.net/problem/1018 Input 10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB Output 12 ① N * M 크기의 board를 8 × 8로 잘나 낼 수 있는 모든 경우의 수 구하기 ex) 9 × 9 크기에서는 4가지 경우가 존재 ② 8 × 8크기로 잘나낸 board에서 색을 바꾸어야할사각형의 개수를 합니다. - 흰색 / 검은색으로 시작하는 경우 중 색이 바뀌는 개수가 더 작은 것을 구합니다. ③ 전체 Case 중 ②에서 구한 값 중 최소값.. 2021. 2. 28.
[BOJ] 백준 1915 가장 큰 정사각형 출처: https://www.acmicpc.net/problem/1915 Input 4 4 0100 0111 1110 0010 Output 4 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com ▶ DP[i][j] = (i,j)를 우측 끝으로 하는 정사각형의 최대 크기의 제곱근 DP[i][j]는 map[i][j] = 1인 지점에서 점화식 DP[i][j] = min(DP[i-1][j], DP[i][j-1.. 2021. 2. 28.
[BOJ] 백준 1793 타일링 출처: https://www.acmicpc.net/problem/1793 Input 2 8 12 100 200 Output 3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251 2 * N 직사각형이 주어질 때, 2×1과 2×2 타일로 채우는 방법의 수 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 z.. 2021. 2. 28.
[BOJ] 백준 2110 공유기 설치 출처: https://www.acmicpc.net/problem/2110 Approach [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다. Binary Search (이분 탐색) Binary Search (이분 탐.. zoosso.tistory.com Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택.. 2021. 2. 28.
반응형

티스토리툴바