![]()
문제 출저 https://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net 문제 풀이 성원이는 다이어트 중이다. 성원이의 현재 몸무게의 제곱 - 기억하는 몸무게의 제곱 = G 이다. 이 때 G를 만족하는 현재 몸무게를 구해야 한다. 투 포인터를 이용해 풀었습니다. long e : 현재 몸 무게 long s : 기억하는 몸 무게 이렇게 두 개의 포인터를 사용하여 e*e - s*s
![]()
문제 출저 https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 문제 풀이 수열이 주어질 때, 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구해야 한다. 투 포인터로 문제를 풀었습니다. end, start를 두 개의 포인터를 이용했습니다. end, start는 모두 0에서 시작합니다. end는 배열의 끝까지 탐색합니다. end 포인터에 걸린 숫자의 갯수를 +1 해줍니다. 만약 숫자의 갯수가 K보다 크다면 start가 움직입니다..
![]()
문제 출저 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 풀이 자연수의 숫자 n이 주어진다. 이 n을 제곱수로 표현할 때, 제곱수의 최소 갯수를 구해야 한다. 제곱수란 1, 4, 9 ... 와 같은 자연수의 제곱으로 만드는 숫자이다. DP를 이용해서 풀었습니다. n의 범위는 1부터 50,000 입니다. int[] dp = new int[50001]을 선언했습니다. dp 배열에 각 숫자의 제곱수의 최소값..
![]()
문제 출저 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 문제 풀이 히스토그램이 주어진다. 이 때, 히스토그램 내부에 가장 넓이가 큰 직사각형의 넓이를 구해야 한다. Stack을 이용해 문제를 풀었습니다. Stack에는 현재 탐색하는 막대보다 작거나 같은 값만이 들어갈 수 있습니다. 히스토그램의 막대의 위치를 Stack에 넣으며 탐색합니다. Stack에 담긴 이전 막대의 높이가 현재 탐색하는 막대의 높이보다 크..
![]()
문제 출저 https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 www.acmicpc.net 문제 풀이 금액 T가 주어집니다. 동전의 금액과 갯수가 K개 주어집니다. 금액 T를 거슬러줄 수 있는 방법을 구해야 합니다. 예제) 20 3 5 3 10 2 1 5 금액 20원과 동전의 금액과 갯수가 3개 주어집니다. 동전의 금액과 갯수는 각각 5원짜리 3개, 10원짜리 2개, 1원짜리 5개입니다. DP를 이용해 풀었습니다. 냅색 알고리즘이 생각나 이를 응용해 풀었습니다..
![]()
문제 출저 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제 풀이 테스트케이스 t가 주어집니다. t만큼 주어진 문제를 풀어야 합니다. 문제는 나라의 개수 n개가 주어집니다. 그리고 항공편이 k개 주어집니다. 모든 나라를 탐색할 수 있는 항공편의 최소 개수를 구해야 합니다. 이 문제는 최소 신장 트리(MST)문제입니다. 최소 신장 트리의 특징은 간선의 갯수는 (정점의 갯수-1) 입니다. 그러므로 정답은 n..
![]()
문제 출저 https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 풀이 n * n 크기의 체스판이 주어집니다. k 개의 기물이 주어집니다. 기물은 행과 열 방향 정보가 주어집니다. 방향은 오른쪽, 왼쪽, 위쪽, 아래쪽 4방향 입니다. 체스판 기물들은 방향대로 움직입니다. 이 때, 기물들을 만나면 기물이 위로 올라타게 됩니다. 아래에 기물이 움직이면 그 기물 위에 있는 기물들도 같이 움직입니다. 체스판에는 흰색, 빨강, 파랑이 각각 숫자 0, ..
![]()
문제 출저 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1
![]()
문제 출저 https://www.acmicpc.net/problem/8394 8394번: 악수 첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 풀이 일렬로 n명의 사람이 있습니다. 양 옆에 있는 사람 중 한 사람만 악수가 가능합니다. 악수를 하는 총 방법의 수를 구해야 합니다. 사람의 수가 n으로 주어지는데 범위가 10,000,000 입니다. 큰 크기에 dp로 문제를 풀 생각을 했고 점화식을 찾았습니다. 사람이 추가될 때 경우의 수는 2개 입니다. 악수를 하거나 악수를 안하거나 2개입니다. 악수를 하지 않은 경우의 수는 옆에 사람이 악수를 한 상태, 악수를 안한 상태 모두 가능합니다. 악수를 한 경우의 수는 옆에 사람이 악수를 안..
![]()
문제 출저 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 풀이 구멍이 n개인 멀티탭이 주어집니다. k 번의 전기용품이 주어집니다. 전기용품은 자신의 차례일 때 멀티탭에 꼽혀야 합니다. 멀티탭에 콘센트를 뽑는 횟수의 최소값을 구해야 합니다. 그리디 방식으로 문제를 풀었습니다. 멀티탭이 비어있을 경우 전기용품을 꽂습니다. 멀티탭이 가득 차 있을 경우 2가지 로직을 수행합니다. 먼저, 멀티탭에 꽂혀있는 전기용품이 다음에 쓰일지를 확인합니다. ..
![]()
문제 출저 https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 문제 풀이 용사의 공격력이 주어집니다. 그리고 방의 정보가 주어집니다. 방에는 포션이 있을 수가 있고 몬스터가 있을 수 있습니다. 포션이 있으면 용사의 공격력과 체력이 올라갑니다. 이 때, 체력은 최대 체력을 넘을 수 없습니다. 몬스터가 있을 경우 몬스터와 전투를 합니다. 용사가 먼저 공격하면서 서로 공격을 주고 받습..
![]()
문제 출저 https://www.acmicpc.net/problem/15748 15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st www.acmicpc.net 문제 풀이 이번 문제는 영어라 구글 번역기와 블로그를 보고 문제를 파악했습니다. 문제에는 농부 존과 그의 친구 ..
