![]()
문제 출저 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 문제 풀이 이번 문제는 영어라 구글 번역기와 블로그를 보고 문제를 파악했습니다. 문제에는 농부 존과 그의 친구 ..
문제 출저 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 문제 풀이 2차원 int 배열이 주어지고 산봉우리의 갯수를 구하는 문제입니다. 산봉우리란 같은 높이를 잇고 각각의 지점이 8방향 지점보다 크거나 같은 지점들입니다. BFS를 통해서 문제를 풀었습니다. 등고선 개념을 생각했습니다. 8방향으로 탐색하면서 같은 크기의 지점들을 이었습니다. 그리고 이 지점들 하나하나 8방향을 탐색해서 높은 게 하나라도 있다면 fa..
![]()
문제 출저 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 문제 풀이 중위 표기식을 후위 표기식으로 바꾸는 문제입니다. Stack을 사용하여 문제를 풀었습니다. Stack operation을 선언하여 기호들을 저장했습니다. StringBuilder sb를 선언하여 후위 표기식을 저장했습니다. 1. 알파밧이 나오면 그대로 sb에 저장합니다. 2. ( 연산자가 나오면 operation에 저장합니다. 3. ) 연산자가 나오면 operation에서..
