https://www.acmicpc.net/problem/3955알고리즘 분류 : 수학, 정수론, 확장 유클리드 호제법❓문제🔅해석확장 유클리드 호제법 알고리즘을 이용한다. (공식 : ax+by=gcd(a,b))방정식에 적용할 a, b, c를 생각해보자면, a와 b는 입력값인 인원수, 한 봉지에 든 사탕 개수로 둘 수 있다.axby인원수인당 나눠줄 사탕 수한 봉지에 든 사탕 수사탕 봉지수ax + 1 = by 아래와 같이 항 정리를 한다.-ax + by = 1 여기서 주의할 점은, 나머지 정의가 0 그래서 a, b에 음수가 들어오지 않도록 x가 음수 값을 가지게 한다.a(-x) + by = 1 이제 확장 유클리드 호제법을 통해 s, t, r 값을 구한다.public static EGResult egcd(l..
https://www.acmicpc.net/problem/14476 알고리즘 분류 : 수학, 정수론, 누적합, 유클리드 호제법❓문제 🔅해석위 문제는 누적합과 유클리드 호제법을 이용하여 풀이해야한다. 먼저 두 수의 최대공약수를 구하는 방법인 유클리드 호제법을 구현한 코드이다.// gcd(a, b) == gcd(b, r) : r = a % bstatic int gcd(int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a;} 이 유클리드 호제법을 통해 나온 최대공약수를 누적합 배열에 담는다. 8 12 24 36 48예를들어, 입력이 위와 같이 들어왔을 때, 8 ~ 48의 최대공약..
❓문제 https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 🔅해석 문제 분류가 DP와 브루트포스 알고리즘으로 분류되어 dfs로 접근해야겠다고 생각했다. 1. 깊이우선탐색으로 지구에서 달까지 가는 경로를 다 탐색한다. 2. 단, 같은 방향으로 2번 이상 갈 수 없으니, 이전 방향과는 다르게 전진해야한다. → 갈 수 있는 방향은 미리 배열로 선언해둔다. dirY = {-1, 0, 1}; 3. 마지막 단계에서 해당 경로의..
❓문제 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 🔅해석 이 문제는 사칙연산만 잘하면 풀 수 있는 문제이다. 이런 잔돈 계산 문제는 늘 계산식이 비슷하니 한문제만 풀면 다른 잔돈 문제를 어렵지않게 풀 수 있을 것이다. 잔돈의 개수를 최소한으로 받아야하므로 잔돈 중 제일 큰 잔돈을 먼저 계산하여 잔돈의 부피를 줄여야 한다. 1. 받을 잔돈에서 제일 큰 잔돈의 개수를 구한다. 예를 들어, 380원 구매하고 1000원을 냈..
❓문제 https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net 🔅해석 참고 영상 https://www.youtube.com/watch?v=YkDv-O4dxfM&t=475s&ab_channel=%EC%9D%B4%EC%83%98%EC%BD%94%EB%94%A9 핵심 모든 구간에 대한 경우의 수는 조건에 맞는 모든 간선을 지나는 횟수의 총합이다. 이 문제는 노드 1(정상)을 제외한 노드 i와 노드 j를 방문할 때 최소 경로의 수로 경우의 수를 구한다...
❓문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 🔅해석 이 문제는 브루트포스 알고리즘에 속하므로 완전 탐색을 하는 문제이다. 그도 그럴것이 주어진 카드의 경우의 수를 다 더해가면서 최대 값을 넘지 않으면서 가장 가까운 값을 찾아야 할 것이다. 그래서 단순하게 for문을 다중으로 돌면서 숫자를 더해줬다. ⭕정답 코드 import java.io.BufferedReader; import java.io.Input..
❓문제 https://www.acmicpc.net/problem/10250 🔅해석 배정될 방의 행과 열을 구하는 문제로 층과 행에서 몇변째 방인지를 구해 합친 결과를 내야한다. 1. 행 구하기(floor) 행은 높이(height)에서 n번째를 나눈 나머지 값이 층 높이(floor)가 나온다. 예를 들어, 높이가 6이고 n번째가 10이라면 6/10 = 1.4 이므로 나머지 값이 4가 높이가 된다. 단, 높이와 n번째의 값이 같다면 나머지 값이 0이 나오는데 이런 경우는, 높이 값만큼 층을 배정해주면 되니깐 floor는 height 또는 n이 된다. 2. 열 구하기(room) 열은 n번째에서 높이(height)를 나눈 값 +1 이 room이 된다. 예를 들어, 높이가 6이고 n번째가 10이라면 6/10 = ..
❓문제 https://www.acmicpc.net/problem/2587 2587번: 대표값2 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + www.acmicpc.net 🔅해석 평균과 중앙값의 개념을 알고 있고 배열을 정렬만 할 수 있다면 쉬운 문제이다. Arrays.sort()로 int 배열을 인자로 전달하면 오름차순으로 정렬된다. int[] num = new int[5]; Arrays.sort(num); 또한, 람다식으로 정렬이 가능하다. 람다식을 사용할 때는 ArrayList에 자연수를 담아야한다. ArrayLis..
https://www.acmicpc.net/problem/25206 25206번: 너의 평점은 인하대학교 컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 그런데 아뿔싸, 치훈이는 깜빡하고 졸업고사를 응시하지 않았다는 사실을 깨달았다! 치 www.acmicpc.net ❓문제 🔅해석 복잡한 논리없이 풀 수 있는 문제이다. 입력 값으로 과목명, 학점, 등급이 공백으로 구분되어 주어지는데 과목명은 계산에 영향을 미치지 않으므로 따로 저장을 하지 않는다. 학점, 등급만 입력시 바로 누적합을 구한다. 다만, 등급은 문자열로 입력되기에 if문이나 switch 문을 통해 실수로 변환한다. 전공평점은 전공과목별 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값으로 계산한다. ..
https://www.acmicpc.net/problem/29813 29813번: 최애의 팀원 2학년이 된 김한양은 한양대학교의 3대 관문 중 하나인 전문학술영어를 수강하게 됐다. 그런데, 갑자기 올해부터는 전학영이 2인1조 팀플로 진행된다는 공지가 떴다. 팀 구성은 자유이지만, 7수 www.acmicpc.net ❓문제 🔅해석 처음에 문제 해석이 어려웠는데 내가 이해한 바로는 1. 2번째 열부터 주어진 알파벳은 팀원을 찾는 학생들이며, 숫자는 n번째 팀원을 찾았다는 것이다. 2. 팀원이 아닐 경우 앞사람이 맨 뒤로 넘어가므로 팀원을 찾는 학생의 순서는 계속 바뀐다. 예제 입력 1에서, A가 3번째 팀원을 찾기 위해 B,C,D,E 가 줄을 선다. A가 3번째 팀원을 찾기 위해 B,C를 뒤로 보냈고 3번째 ..
