전체 글 (29) 썸네일형 리스트형 [C++] BOJ-1202 문제풀이 1. pair형 변수에 보석의 정보를 입력하고, backpack 변수에 가방의 정보를 입력한다. 2. 보석배열은 무게에 따라 정렬을 해주고 backpack 배열도 마찬가지로 정렬을 해준다.(오름차순) 3. 가방의 개수에 따라 반복문을 돌리는데 여기서 현재 선택된 가방에 넣을 수 있는 모든 보석의 가격을 우선순위큐에 집어넣습니다. 4. 그렇게 되면 우선순위 큐의 top에 위치한 보석이 현재 선택된 가방에 넣을 수 있는 보석 중 가장 비싼 보석이기 때문에 sum 변수에 더해주고 pop 해줍니다. 5. 위의 과정을 모든 가방에 대해서 반복합니다. 1시간 6분 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30.. [C++] BOJ-1655 문제풀이 1. max_heap과 min_heap을 2개 선언한다. 2. min_heap의 top이 max_heap의 top보다 작으면 두 우선순위 큐의 탑을 스왑해준다. 3. 이 과정을 진행하면 max_heap의 top은 항상 가운데 숫자이기 때문에 max_heap의 top을 출력하면 된다. (직접 그려보면서 이해하면 쉽다.) 41분 01초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); priority_queue max_.. [C++] BOJ-1715 문제풀이 1. 우선순위 큐에 각각의 카드 묶음의 크기를 집어넣는다. 2. 우선순위 큐에 들어있는 카드묶음 중 가장 작은 것들중 2개를 더하고 그 카드묶음을 다시 우선순위 큐에 넣는다. 3. 이 과정을 반복하면서 sum에 계속 더해주고 더 이상 비교할 수 있는 카드 묶음이 없다면 sum을 출력한다. 27분 14초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); priority_queue pq; int N, num, sum = 0; cin >> N.. [C++] BOJ-2529 문제풀이 1. 재귀함수로 모든 경우의 수를 탐색해서 부등호의 조건에 맞는 수열을 찾는다. 2. k가 0일 경우를 제외하고 수열의 k-1번째 요소와 현재 들어갈 숫자를 비교해서 부등호의 조건에 맞다면 수열에 집어넣는다. 3. 제일 마지막에 저장된 수열과 제일 처음 저장된 수열을 출력한다. 4. 재귀함수를 통해 0부터 차근차근 탐색하기 때문에 처음과 마지막에 저장된 수열을 그대로 출력해도 답이 나온다. 57분 49초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 .. [C++] BOJ-2512 문제풀이 1. 기본적인 binary search(이분탐색 문제) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include #include using namespace std; int main(){ ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, money, st, end, sum = 0; cin >> N; int arr[N]; for(int i = 0; i> arr[i]; } sort(arr,arr+N); cin >> money; st.. [C++] BOJ-9569 문제풀이 1. 3차원배열에서 bfs를 돌려주는 문제다. 2. 큐에 x,y,z좌표를 넣고 인접해있는 값이 0(익지 않은 토마토)이면 (현재 좌표값) + 1 을 해준 값을 인접하고 있는 배열에 집어넣는다. 3. 이 과정을 반복하여 마지막에 좌표에 넣었던 숫자를 반환한다. 4. 모든 과정이 끝난 후에도 0이 발견되면 -1을 반환한다. 38분 18초 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 7.. [C++] BOJ-1966 문제풀이 1. 중요도를 저장할 수 있는 priority_queue와 (문서의 처음 위치, 중요도)를 저장할 수 있는 queue를 2개 생성한다. 2. 우선순위큐는 가장 높은 우선순위가 top의 위치에 존재하기때문에 우선순위큐의 top과 queue에 있는 요소의 중요도를 체크해서 다르면 큐의 뒤로 넘기고 같으면 pop 한다. 3. pop이 될 때마다 count를 해주고 찾고싶은 문서가 pop이 되면 반복문을 종료한다. #include #include using namespace std; int main(){ int T; cin >> T; for(int test = 0; test < T; test++){ priority_queue pq; queue q; int N,M; int importance; int c.. [C++] BOJ-1932 문제풀이 1. 가장 왼쪽에 있는 숫자와 가장 오른쪽에 있는 숫자는 경우의 수가 하나이기 때문에 바로 위에 배치된 숫자만 더하면 된다. 2. 그 외의 숫자들은 모든 경우의 수를 계산해서 가장 큰 수를 다음 줄에 저장한다. #include #include using namespace std; int main(){ int n; cin >> n; int dp[501][501]; for(int i = 0; i dp[i][j]; } } for(int i = 1; i 이전 1 2 3 4 다음
