본문 바로가기

C++105

[C++] 프로그래머스 : 키패드 누르기 https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 문제 풀이 왼손과 오른손의 좌표와 누를 버튼까지의 거리를 저장하는 구조체를 선언한다. 발생하는 경우는 3가지이다. 1. 왼쪽(1, 4, 7)을 누르는 경우 2. 오른쪽(3, 6, 9)을 누르는 경우 3. 가운데(2, 5, 8, 0)를 누르는 경우 1번 .. 2021. 9. 13.
[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.

티스토리툴바