누적 합14 [백준]31997: 즐거운 회의 - JAVA https://www.acmicpc.net/problem/31997 풀이N명의 사람들이 회의에 입장하고 퇴장하는 시간이 주어진다. M개의 서로 친한 사람들의 쌍이 주어진다. 먼저 각 사람별로 회의에 입장하고 퇴장하는 시간의 정보를 저장한다. `T + 1` 길이의 배열을 만들어 서로 친한 사람들의 쌍을 입력받으면서 해당 배열에 값을 저장한다. 예를 들어 c와 d가 친하다면 c와 d의 회의 입장/퇴장 정보를 확인하여, 두 사람이 회의에 함께 있는 시간(start)은 `두 사람이 입장하는 시간을 비교하여 큰 값`, 두 사람이 회의에 함께 있다가 함께 하지 않는 시간(end)은 `두 사람이 퇴장하는 시간을 비교하여 작은 값`이 된다. 다만, start가 end보다 같거나 크다면 두 사람은 서로 함께 있지 않는.. 2024. 9. 2. [백준] 30960: 조별 과제 - JAVA https://www.acmicpc.net/problem/30960 풀이N명의 학생들의 조를 편성해야한다. 1개의 조만 3명으로 편성되고 다른 조들은 2명으로 편성된다. 학생에게 숫자가 부여되는데 각 조 안에서 (최댓값 - 최솟값)이 해당 조의 어색함이 된다. 어색함의 합의 최소가 되도록해야한다. 먼저 입력받은 배열을 정렬했다. 정렬 후 2개의 배열을 만들어서 하나는 앞에서부터 시작, 하나는 뒤에서부터 시작하여 누적합을 담았다. 누적합은 어색함들의 합을 더해줬다. `left[i] += (arr[i] - arr[i-2])` 이런식으로 어색함을 더해줬고, i는 2찍 증가시키면서 진행했다. 누적합 배열 2개를 만든 후, 어느 지점에서 3명인 조를 시작해야 어색함이 최소가될지 구해줬다. 메모리: 84096K.. 2024. 6. 25. [백준] 28449: 누가 이길까 - JAVA https://www.acmicpc.net/problem/28449 풀이HI 팀과 ARC 팀의 모든 사람들끼리 한번씩 대결하여 N X M회의 대결이 성사된다. HI팀이 이기는 횟수, ARC팀이 이기는 횟수, 무승부하는 횟수를 구해야 한다. 각 팀의 점수를 입력받아 각각 정렬했다. HI팀을 순회하면서 HI팀원의 점수를 타겟으로 하여 ARC팀에서 해당 점수와 같은 점수가 있는지 찾았다. 이때, 이분탐색을 이용하여 같은 점수가 시작되는 지점(drawStart), 같은 점수가 끝나는 지점(drawEnd)를 각각 찾았다. drawStart보다 작은 값들은 HI팀이 이기게 되고, drawEnd보다 큰 값들은 ARC팀이 이기게 된다. 메모리: 41148KB시간: 700ms언어: Java 11import java.i.. 2024. 6. 18. [백준] 2015: 수들의 합 4 - JAVA https://www.acmicpc.net/problem/2015 풀이주어진 수열에서 부분 수열의 합이 k가 되는 경우를 찾는 문제이다. 누적합과 맵을 이용해 해결했다. ```sum[i]```에서 k를 뺀 값이 이전에 등장한 적이 있는지를 확인한다. 현재 누적합이 ```sum[i]```라고 할 때, ```sum[i]-k```가 이전에 등장한 적 있다면 그 구간의 합이 k라는 것을 의미한다. 메모리: 33452KB시간: 348ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br =.. 2024. 6. 10. [백준] 25682: 체스판 다시 칠하기 2 - JAVA https://www.acmicpc.net/problem/25682 풀이M x N 사이즈의 보드가 주어지고, K x K 의 크기로 잘라 이 구역을 체스판 모양으로 만들어야한다. 뭔가 이 말을 이해하는데 오래걸렸다... 체스판은 흰색 검은색이 번갈아 나온다. 체스판의 첫 칸을 (0, 0)이라고 한다면, 첫칸이 흰색이면 격자의 행 + 격자의 열 번호를 더했을 때 짝수이면 흰색, 홀수이면 검은색이다. 첫칸이 검은색이면 마찬가지 방식으로 반대로 된다. BW로 이루어진 보드를 입력받으면서 위의 규칙에 맞게 첫칸이 흰색인 배열, 첫칸이 검은색인 배열에 각각 넣었다. 이 배열에서 1이 의미하는 것은 격자의 색깔이 맞지 않아 새로 칠해야 한다는 의미이다. 잘 맞게 칠해져있는 것은 0으로 한다. 검은색, 흰색 각각 2차.. 2024. 5. 19. [프로그래머스] 파괴되지 않은 건물 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이N X M 크기의 영역이 주어지고, 각 영역을 사각형 크기의 영역을 정해 일정 수를 더하고 빼주게 된다. 누적합을 이용하는 문제였다. (a, b) 부터 (c, d) 까지의 사각형에 5씩 더해주기 위해서는arr[a][b] += 5arr[a+1][b+1] += 5arr[a][b+1] -= 5arr[a+1][b] -= 5위처럼 더해주면 된다. 이렇게 수를 저장한 뒤 행마다 왼쪽에서 오른쪽으로 누적합해주.. 2024. 5. 18. [프로그래머스] 광고 삽입 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이시청자의 시청 시작, 종료 시각이 주어지고, 광고 지속 시간이 주어진다. 광고 지속 시간동안 누적 재생 시간이 가장 많은 구간을 골라야 한다. 누적합을 이용했다. 시청 시작시간에 +1 하고, 종료시간에 -1을 해놓고 누적합 배열을 끝까지 가면서 `preSum[i] += preSum[i - 1]` 해줬다. 누적합 배열을 완성한 후, 0 ~ 광고시간 까지를 첫 기준으로 삼아 1씩 늘려가면서 비교하며 .. 2024. 5. 18. [백준] 25708: 만남의 광장 - JAVA https://www.acmicpc.net/problem/25708 풀이길을 가로 2개, 세로 2개 만들어야 한다. 가로와 세로 각각 누적합을 만들어놓았다. 4중for문을 통해 up, down, left, right 를 탐색하여 구해놓은 누적합을 더해주고 겹치는 부분을 원 배열에서 찾아 빼주었다. 길로 둘러쌓인 부분의 개수를 더해야 하므로 `(down-up-1)\*(right-left-1)` 만큼 더해주었다. 메모리: 16892KB시간: 312ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedRe.. 2024. 5. 17. [백준] 1749: 점수따먹기 - JAVA https://www.acmicpc.net/problem/1749 풀이n \* m 행렬에서 직사각형의 구간을 잡아 구간의 합의 최대값을 구하는 문제이다. 입력을 받으면서 n \* m 행렬을 누적합으로 저장했다.board[i][j] = Integer.parseInt(st.nextToken()) + board[i - 1][j] + board[i][j - 1] - board[i - 1][j - 1];탐색을 해서 최댓값을 구해야 하는데 구간의 길이가 정해져 있지 않으므로 행시작/끝, 열시작/끝 4중for문을 통해 탐색해야 한다. 열 시작을 rs, 끝을 re, 행 시작을 cs, 끝을 ce로 하여 정답을 갱신했다.ans = Math.max(ans, board[re][ce] - board[rs - 1][ce] - b.. 2024. 5. 16. [백준] 3020: 개똥벌레 - JAVA https://www.acmicpc.net/problem/3020 풀이석순과 종유석이 번갈아 나오는 동굴을 장애물을 파괴하면서 지나가야한다. 높이별로 만나는 장애물의 개수를 세어 최솟값을 찾는 문제이다. 처음에 누적합으로 문제를 풀었고, 이분 탐색으로 푸는 방법이 있다고하여 찾아보았다. - 이분 탐색 이분 탐색으로 풀기 위해서는 석순과 종유석을 따로 배열에 담아준다. bottom배열에 석순을, top배열에 종유석을 담았다. 이분탐색을 위해 배열을 정렬한 뒤 1부터 H까지 높이을 key로 하여 이분탐색을 진행한다. 석순과 종유석을 각각 진행하여 해당 key값(key값보다 크거나 같은 첫번째 인덱스)을 찾아 arr.length - rigth을 반환하면 해당 구간의 장애물의 개수를 구할 수 있다.. 2024. 5. 14. 이전 1 2 다음