본문 바로가기

C++106

[백준][그리디] 18310 안테나 c++ 구현 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 문제 문제 풀이 최적부분 구조는 정렬했을 때 크기가 짝수이면 중간 index-1 크기가 홀수이면 가운데 중간 index이다. 코드 구현 #include #include #include #include using namespace std; vector arr; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, num, i, sum=.. 2024. 3. 19.
[백준][그리디] 11501 주식 c++ 구현 목차 https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 문제 풀이 시 주의해야 할점 이중반복문을 돌리게 되면 시간 복잡도가 O(N^2)이 나와 시간초과로 틀리게 된다. 따라서 전처리를 통해 자기보다 큰 것이 없는지 있는지 정해주어 풀면시간복잡도가 O(N)으로 풀리게 도힌다. 문제 풀이 오늘보다 뒷날에 주가가 더 큰 것이 있다. 매수한다. 오늘보다 뒷날에 더 큰 것이 없다. 주식이 있다면 판다. 주식이 없다면 나둔다. 이런식의 최.. 2024. 3. 16.
[백준][이분 탐색] 1484 다이어트 c++구현 목차 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 문제 풀이 시 주의할 점 현재 몸무게와 그 전 몸무게가 자연수인 것을 주의 해야 한다. 처음에 식을 풀어서 이분 탐색을 했는데 식을 풀지말고 A^2-B^2 형태로 이분탐색을 해야한다. 문제 풀이 내가 탐색하고자 하는 현재몸무게를 A, 그 전 몸무게를 B라고 놓으면 G = A^2-B^2의 형태가 나온다. 그 후 A를 기준으로 B를 이분탐색해주면 된다. 코드구현 #include #include #incl.. 2024. 3. 14.
[백준][구현] 14719 빗물 c++구현 목차 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 문제 구현 방향 보이는 대로 바닥을 채우고 블록은 1로 표시하여 2차원 배열로 만들어 직접 반복문을 통해 카운트하는 방식으로 문제를 풀었다. 문제 풀이 시 주의점 바닥이 항상 막혀있다는 점과 언제부터 카운트를 할지 시점만 잘 주의해 주면 된다. 코드 구현 #include using namespace std; int ml = 0; //빗물 세어주기 int main() {.. 2024. 3. 13.
728x90

티스토리툴바