본문 바로가기

Algorithm 문제풀기111

[JAVA] 성냥개비 ::: DP, 그리디 [ 문제 ]https://www.acmicpc.net/problem/3687   [ 제출코드 ]   [ 풀이 ]성냥개비 개수만들 수 있는 숫자21374452, 3, 560, 6, 978성냥개비 개수만들 수 있는 최솟값810DP(2) = 1DP(6) = 0918DP(2) = 1DP(7) = 81022DP(5) = 2DP(5) = 21120DP(5) = 2DP(6) = 01228DP(5) = 2DP(7) = 81368DP(6) = 6DP(7) = 8  1. 가장 작은 수 구하기성냥개비 개수가 6개인 경우, 숫자가 가장 앞에 와야하는 경우, 가장 작은 수 : 6이 외, 가장 작은 수 : 0아래 결과 중 가장 작은 수를 DP(i)에 저장합니다.DP(i - 2) + plusNumber(2),DP(i - 3) + .. 2024. 7. 24.
[JAVA] 수들의 합 5 ::: 수학, 두 포인터 [ 문제 ]https://www.acmicpc.net/problem/2018   [ 제출코드 ]   [ 풀이 ]1. 두 개의 포인터(시작, 끝)를 선언합니다.2. 연속된 자연수의 합인 sum을 구합니다.3. sum이 n과 같다면 answer에 1을 증가시킵니다.4. sum이 n보다 작다면 끝 포인터(endP)를 1 증가시킨 뒤 sum에서 증가시킨 끝 포인터(endP)를 더해줍니다.5. sum이 n보다 크다면 sum에서 시작 포인터(startP)만큼 뺀 뒤 시작 포인터(startP)를 1 증가시킵니다. 2024. 6. 10.
[JAVA] 나머지 합 ::: 수학, 누적합 [ 문제 ]https://www.acmicpc.net/problem/10986   [ 제출코드 ]   [ 풀이 ]누적 합을 구한 배열(sumArr)을 생성합니다.sumArr에서 m으로 나눈 나머지의 값으로 이루어진 배열(modArr)을 생성합니다.modArr에서 0의 개수만큼 answer에 더해줍니다.modArr에서 i 위치가 0이라는 의미는 0번째부터 i번째까지의 합이 m으로 나누었을 때 나누어 떨어진다는 의미입니다.modArr에서 같은 수가 2개 이상인 경우 xC2를 구해서 answer에 더해줍니다.S[i] % m의 값과 S[j] % m의 값이 같다면 (S[i] - S[j]) % m은 0입니다.즉, 구간 합 배열의 원소(sumArr)를 m으로 나눈 나머지로 업데이트(modArr)하고 S[i]와 S[j.. 2024. 6. 2.
[JAVA] 구간 합 구하기 5 ::: DP, 누적 합 [ 문제 ]https://www.acmicpc.net/problem/11660   [ 제출코드 ]   [ 풀이 ]2차원 배열에서 각 부분까지의 누적합을 구한 뒤 계산합니다. 아래 배열(arr)이 주어졌을 때, 1234234534564567 다음과 같이 누적합 배열(sumArr)을 따로 생성해 줍니다.sumArr[i][j]를 채우는 방법은 arr[i][j] + sumArr[i][j - 1] + sumArr[i - 1][j] - sumArr[i - 1][j - 1] 입니다.13  => 1 + 26  => 1 + 2 + 310  => 1 + 2 + 3 + 43  => 1 + 28  => 3 + 3 + 3 - 115  => 4 + 6 + 8 - 3246  => 1 + 2 + 315274210  => 1 + 2 .. 2024. 5. 31.
[JAVA] 구간 합 구하기 4 ::: 누적합 [ 문제 ]https://www.acmicpc.net/problem/11659   [ 제출코드 ]   [ 풀이 ]각 배열 위치의 누적합을 저장하는 배열을 따로 생성합니다.주어진 구간의 합을 구하기 위해 누적합 배열을 사용하면 됩니다. 예를 들어, 1번째 ~ 3번째 구간의 합을 구할 때는 "누적합의 3번째 위치"를 반환해주면 됩니다.2번째 ~ 4번째 구간의 합을 구할 때는 "누적합의 4번째 위치"에서 "누적합의 1번째 위치"를 빼주면 됩니다. 2024. 5. 29.
[JAVA] 덩치 ::: 구현, 브루트포스 [ 문제 ]https://www.acmicpc.net/problem/7568   [ 제출코드 ]   [ 풀이 ]1. {위치, 몸무게, 키, 순위}를 담을 수 있는 Person 클래스를 만듭니다.2. 몸무게를 기준으로 오름차순으로 정렬합니다.3. 반복문으로 비교하면서, 현재 비교 대상인 사람보다 키와 몸무게 모두 큰 사람의 수만큼 순위에 더해줍니다.4. 위치에 맞게 정답을 출력합니다. 예를 들어서, 입력이 다음과 같다고 가정해 봅시다.655 18154 18156 18155 17956 18254 190 위의 입력은 2번에 의해 다음과 같이 정렬할 수 있습니다.6, 54 1902, 54 1814, 55 1791, 55 1815, 56 1823, 56 181 여기서 주의할 점은 6번과 2번 중 키는 6번이 더 .. 2024. 4. 26.
[JAVA] 부녀회장이 될테야 ::: DP [ 문제 ] https://www.acmicpc.net/problem/2775 [ 제출코드 ] [ 풀이 ] 0번째 행은 0층이고, 0열은 제외하고 1열부터 시작한다고 생각하면 됩니다. 이렇게 거주민 수를 담은 배열을 만들어 준 뒤, 정답을 요구하는 호수의 거주민만 찾으면 됩니다. 2024. 4. 15.

티스토리툴바