문제 풀이262 [C++] 백준 18111번 : 마인크래프트 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 문제 풀이 기본적인 브루트 포스 문제이다. 기준이 되는 높이에서 걸리는 시간을 구해서 계속 비교해 가장 작은 값을 출력하면 된다. 입력받을 때 최소 높이와 최대 높이를 구해 놈으로 반복 횟수를 최소화할 수 있다. 최소가 되는 시간이 여러 경우가 있을 수 있어 그 중 가장 높은 높이일 때를 출력해야 한다. (제거 시간 + 쌓는 시간)이 최소 시간과 같을 때도 최신화 함으로 가장 높은 높이를 출력할.. 2021. 8. 30. [C++] 백준 2805번 : 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 풀이 이전 문제(BOJ 1654 : 나무 자르기)와 비슷한 문제이다. 다른 점은 딱 맞아떨어지지 않는다는 것이다. 적어도 M미터의 높이의 나무를 가져가야 한다. 즉, 1미터의 나무가 필요할 때 {1, 2, 2} 높이의 나무들이 주어진다면 1미터의 높이에서 잘라야 한다. 느낀 점 삼항 연산자를 사용해서 중간의 번거로운 계산을 줄였다! 이전과 코드가 똑같아.. 2021. 8. 5. [C++] 백준 1654번 : 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이 N개의 랜선을 만드는데 그 길이를 최대로 만들어야 한다. 브루트 포스로 풀 수 있지만 무조건 시간 초과가 발생한다. 이진 탐색으로 탐색 횟수를 줄여야 한다. 가장 긴 길이와 가장 짧은 길이(1) 사이에 답이 존재한다. 이분 탐색을 통해서 그 중간 값과 비교할 텐데 잘랐을 경우 N개가 되는 값이 여러 개 존재한다. 그중에서 최댓값을 찾아야 해서 잘랐을 때 N개.. 2021. 8. 5. [C++] 백준 10816번 : 숫자 카드 2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 풀이 숫자 카드의 개수를 구하는 문제이다. map을 구현하면 아주 쉽게 풀 수 있다. 느낀 점 다른 분들은 lower bound와 upper bound로 풀었다. C++ STL에서 지원하기 때문에 아주 쉽게 풀 수도 있다. 나는 보자마자 생각난 게 map이어서 그냥 map으로 풀었다! 코드 #include #include using namespace std;.. 2021. 8. 5. [C++] 백준 1920번 : 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 풀이 이분 탐색의 쉬운 문제이다. 이분 탐색 시에는 정렬이 되어야 한다는 점만 기억하면 된다! 느낀 점 qsort로 정렬할 때는 틀렸다고 나와서 그냥 sort를 사용했는데 맞았다. 어떤 것이 잘못됐는지 모르겠다. 코드 #include #include using namespace std; int n, m; long long tmp; long lo.. 2021. 8. 3. [C++] 백준 2740번 : 행렬 곱셈 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 문제 풀이 쉬운 행렬의 곱셈을 구하는 문제이다. 느낀 점 크게 어렵진 않으나 행렬 연산을 줄이는 방법으로 '스트라센 알고리즘'이 있다. 추가적인 공부가 필요할 것 같다. 코드 #include using namespace std; int n, m, k; int m1[101][101]; int m2[101][101]; int m3[101][101]; int main() { ios_b.. 2021. 7. 30. 이전 1 ··· 25 26 27 28 29 30 31 ··· 44 다음