본문 바로가기

분류 전체보기

 (236)
C++[백준]2243번 사탕상자 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 솔루션 처음에 특정 사탕을 꺼낼 방법을 고민을 했다. 그런데, 개수를 저장하는 세그먼트 트리를 구성하면, 1부터 특정 맛 까지 총 몇개가 있는지 알 수 있다. 이 점을 이용해서 세그먼트 트리를 만들고, 세그먼트 트리를 갱신한다면 풀 수 있을 것이라 생각했다. 1) A가 1일 때, 사탕 상자에서 사탕을 빼내는 경우이기 때문에, 왼쪽노드는 더 맛있는 사탕이 있는 총 개수이다..
C++[백준]2244번 민코프스 합 https://www.acmicpc.net/problem/2244 2244번: 민코프스키 합 첫째 줄에 두 다각형 A와 B의 꼭짓점 개수 N과 M이 주어진다. (3 ≤ N, M ≤ 1,000) 다음 N개의 줄에는 다각형 A를 이루는 꼭짓점의 좌표가, 그 다음 M개의 줄에는 다각형 B를 이루는 꼭짓점의 좌표가 주 www.acmicpc.net 솔루션 볼록껍질을 풀 수있다면 이 문제도 쉽게 풀 수 있다. 이 문제는 두개의 다각형 좌표가 들어오면 두개의 좌표의 모든 합을 각 좌표의 점으로 계산하면 된다. 1) a 다각형의 점을 입력 받는다. 2) b 다각형의 점을 입력 받는다. 3) a를 i ->N , b->M 이중 반복문 통해서 모든 좌표의 합을 배열에 넣는다. 4) 컨베스헐을 만든다. 코드 #define l..
C++[백준]9345번 디지털 비디오 디스크(DVDs) https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 솔루션 일반적인 구간 세그먼트 트리를 생각헀다가 해법을 떠올리기 힘들어서 꽤나 고생했다.. 결국은 세그먼트트리를 두개를 이용해서 문제를 해결 할 수 있는 아이디어를 얻었다. 한개는 구간에서의 최대값을 저장하는 세그먼트트리, 다른 한개는 구간의 최소값을 저장하는 세그면트 트리를 이용하였다. 1) 각 배열에 arr[i] = i 로 값을 채워주고 min, m..
C++[백준]3653번 영화 수집 https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 솔루션 세그먼트 트리를 공부하며 문제를 풀고 있다. 나는 이 문제를 세그먼트 트리를 이용해 해결하였다. 1) N이 들어오면, 책의 번호를 1 = N, 2=N-1, ... N = 1 이렇게 저장 할 배열을 하나 선언하고, 배열에 값을 채운다. 2) 그리고 세그먼트 트리를 만든다. 각각의 리프노드의 값은 1로 하고, 총 개수를 세는 세그먼트 트리를 만든다. 3) M을 입력 받을 때 다음의 과정..
C++[백준]3006번 터보소트 https://www.acmicpc.net/problem/3006 3006번: 터보소트 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다 www.acmicpc.net 솔루션 나는 세그먼트 트리 + 정렬 1) 먼저 배열에 입력을 받으면서 인덱스도 저장을 한다. 2) 정렬을 한다. 3) 세그먼트 트리 리프노드를 1개로 가정하고 세그먼트 트리를 만든다. 4) 아래의 과정을 반복한다. 4-1) 짝수일 때는 i/2인덱스를 참조하여 해당 인덱스가 어디에 있는지 알 수 있으니, l=0,r =인덱스 로 설정하여 구간의 합을 구해준다. 4-2) 홀수 일 땐 N-i/..
C++[백준]12873번 기념품 https://www.acmicpc.net/problem/12873 12873번: 기념품 백준이는 BOJ 알고리즘 캠프 참가자 중 한 명에게 기념품을 주려고 한다. 하지만, 많은 참가자 중에서 어떤 사람을 뽑아서 기념품을 줘야하는지 고민이 되기 시작했다. 따라서, 백준이는 게임을 www.acmicpc.net 솔루션 나는 deque를 이용해 접근을하였다. 1) 먼저 dequ에 1~N 까지 넣어준다. (push_back()) 2) t=1 턴 부터 시작해서 N-1턴 까지 반복하면서 아래의 과정을 반복한다. 2-1) t^3을 구한다. 2-2) 해당 값을 (N명 - t턴) 값으로 나눠준다. 2-3) 나머지 만큼 dq.push_back(dq.front()), dq.pop_front() 를 해준다. 3) dq에 남은..
C++[백준]14939번 불 끄기 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 솔루션 대체 어떻게 푸는건지? 고민을 한참 하다 다른 블로그에 글을 보았다. 좋은아이디어로 접근 하는 방법을 찾을 수 있었는데, dfs + 비트 마스킹으로 해결하는 방법이다. 타 블로그의 솔루션만 봤었기에, 풀이가 깔끔하지 않을 수 있다. 1) 먼저 0번째 행에 대해서 2^10가지의 경우를 다 해본다. - 불을 키거나(카운트 증가), 끄거나 (카운트 그대로) 둘 중 한가지의 경우다. 2..
C++[백준]9527번 1의 개수 세기 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 솔루션 시간을 쏟았던 문제.. 나는 먼저 각 비트마다 1의 개수를 세어 주었다. 1 = 1개 10 = 2개 100 = 5개 1000 = 13개 여기서 규칙을 찾아내야 했다. 먼저 10에서 100으로 증가 할 때, 걸치는 수를 생각해 보자. 10, 11 뿐이고, 100에서 1000으로 증가 할 때는 100, 101, 110, 11 이다. 100에서 1000으로 증가할 때 맨..

티스토리툴바