전체 글242 [백준] 12913: 매직 포션 - JAVA https://www.acmicpc.net/problem/12913 풀이0번 도시에서 1번 도시까지 가장 빠른 시간에 가야 한다. 포션을 마실 수 있는데 마시게 되면 한 도시에서 다른 도시로 이동하는데 드는 시간을 반으로 줄일 수 있다. n개의 도시, 포션 사용 가능 개수 k가 주어진다. 즉, 이차원배열을 `dist[n][k + 1]`로 선언하여 포션을 사용한 개수마다 체크해주어야 한다. 우선 도시마다 걸리는 시간이 모두 양수이기 때문에 0번 도시부터 모든 도시까지 최소 시간을 구할 수 있는 다익스트라 알고리즘을 적용했다. 다음 도시로 이동할 때 포션을 쓰지 않는 경우, 쓰는 경우를 나눠 진행해야 한다. 포션을 쓰는 경우는 현재 도시에 오는데 쓰인 포션의 개수가 k보다 작은 경우에만 가능하다. 메모리:.. 2024. 9. 10. [백준]2262: 토너먼트 만들기 - JAVA https://www.acmicpc.net/problem/2262 풀이n명의 선수들의 랭킹이 주어진다. 2명씩 대결을 붙여 우승자를 가리는 토너먼트를 만들어야 한다. 1. 랭킹이 가장 낮은 선수를 찾는다.2. 해당 선수의 좌, 우를 살펴 차이가 적게나는 사람과 대결을 한다.3. 선수가 1명 남을때까지 반복한다. 위의 과정으로 풀 수 있었다. 예제에는 `1 6 2 5 3 4` 로 주어졌다. 첫 번째로 6을 골라 양 옆에 있는 1과 2 중 2를 선택하여 대결한다. `1 2 5 3 4`가 되고, 같은 방식으로 5를 골라 3과 대결한다. 1 6 2 5 3 4 -> 6 vs 2 (4)1 2 5 3 4 -> 5 vs 3 (2)1 2 3 4 -> 4 vs 3 (1)1 2 3 -> 3 vs 2 (1)1 2 -> 2 v.. 2024. 9. 9. [백준]3151: 합이 0 - JAVA https://www.acmicpc.net/problem/3151 풀이N개의 숫자들 중 3개를 선택하여 그들의 합을 0으로 만드는 경우의 수를 찾는 문제이다. 배열에 숫자들을 저장하여 정렬한다. 첫 번째 숫자를 선택하고, 그 다음 숫자를 left, 배열의 끝 숫자를 right로 놓고 left와 right를 조정하여 합이 0이 되는 수를 찾는다. 선택한 숫자를 node라고 할 때, `node + arr[left] + arr[right]` 가 0이 되는 경우를 찾아 정답을 증가시킨다. `arr[left]` 와 `arr[right]`가 같은 경우에는 left부터 right까지의 수가 n개라고 할 때 nC2의 조합을 구하는 것과 같다. 처음 선택한 수를 0부터 시작하여 증가시키면서 값이 0보다 커질 때까지 실행.. 2024. 9. 3. [백준]31997: 즐거운 회의 - JAVA https://www.acmicpc.net/problem/31997 풀이N명의 사람들이 회의에 입장하고 퇴장하는 시간이 주어진다. M개의 서로 친한 사람들의 쌍이 주어진다. 먼저 각 사람별로 회의에 입장하고 퇴장하는 시간의 정보를 저장한다. `T + 1` 길이의 배열을 만들어 서로 친한 사람들의 쌍을 입력받으면서 해당 배열에 값을 저장한다. 예를 들어 c와 d가 친하다면 c와 d의 회의 입장/퇴장 정보를 확인하여, 두 사람이 회의에 함께 있는 시간(start)은 `두 사람이 입장하는 시간을 비교하여 큰 값`, 두 사람이 회의에 함께 있다가 함께 하지 않는 시간(end)은 `두 사람이 퇴장하는 시간을 비교하여 작은 값`이 된다. 다만, start가 end보다 같거나 크다면 두 사람은 서로 함께 있지 않는.. 2024. 9. 2. [백준] 22352: 항체 인식 - JAVA https://www.acmicpc.net/problem/22352 풀이숫자로 채워진 N x M 크기의 격자가 2개 주어진다. 첫 번째 격자를 before, 두 번째 격자를 after라는 이름으로 이차원 배열에 저장했다. 문제의 내용은 before의 어떤 한 점에 백신을 놓는다면, 인접한 영역 중 같은 숫자의 영역들이 함께 동일한 값으로 업테이트 된다는 것이다. 업데이트 하였을 때 입력에서 주어진 after와 같으면 YES, 다르면 NO를 출력하면 된다. (0, 0) 부터 순회하면서 before와 after가 처음으로 달라지는 부분을 찾았다. 해당부분부터 bfs탐색을 통해 인접한 같은 값의 영역들을 after에 해당하는 값으로 바꿔주었다. 그 후, 다시 (0, 0) 부터 before와 after를 비교하.. 2024. 8. 19. [백준] 10881: 프로도의 선물 포장 - JAVA https://www.acmicpc.net/problem/10881 풀이세 개의 선물을 한 상자에 넣어 포장해야 한다. 선물 세 개를 상자에 넣는 방법은 두 가지 경우로 생각해볼 수 있다. `ABC` 처럼 일렬로 놓는 방법과 A와 B를 위아래로 쌓고, C를 옆에 놓는 방법이 있다. 순열을 구해 3개의 선물의 순서를 구한다. 가로, 세로 길이가 주어진 선물을 그대로 놓을지 회전시켜 놓을지 `pos`배열에 저장하면서 순열을 구했다. 선물들의 순서와 회전여부가 주어지면 놓는 방법 2가지 경우에 필요한 상자의 크기를 구해 정답을 갱신했다. 메모리: 28108KB시간: 352ms언어: Java 11import java.io.*;import java.util.*;public class Main { stati.. 2024. 8. 13. [백준] 15671: 오델로 - JAVA https://www.acmicpc.net/problem/15671 풀이익히 알고있던 오델로 게임을 시뮬레이션하는 문제였다. 예를 들어 `BWWW` 와 같은 줄이 있을 때 오른쪽 끝에 B를 위치한다면 `BWWWB` 처럼 검정 돌이 흰 돌을 감싸 잡아먹게된다. 둘러쌓인 흰 돌이 검정색으로 바뀌게 되고 `BBBBB`가 된다. 검정 돌부터 시작하여 돌을 놓는 좌표가 주어지는데, 돌을 놓을 때 대각선까지 팔방탐색하여 처음 검정 돌을 만나면 이전의 흰 돌들을 검정색으로 바꾸고, 빈칸을 만난다면 패스한다. 최종 보드판의 상태와 검정, 흰 돌중 어느 돌이 많아 승리하는지 구하면 된다. 메모리: 14304KB시간: 104ms언어: Java 11import java.io.*;import java.util.*;publi.. 2024. 8. 13. [백준] 20208: 진우의 민트초코우유 - JAVA https://www.acmicpc.net/problem/20208 풀이집의 위치와 우유의 위치가 주어진다. 체력이 0이 되면 이동을 할 수 없다. 우유를 먹으면 일정 체력이 회복되는데 최대한 많은 우유를 먹고 집으로 돌아와야 한다. 처음에는 dfs로 풀이를 했는데 시간초과가 발생했다. 문제의 조건을 다시 보니 우유의 개수가 10개를 넘지 않는다는 것을 확인했다. 지도를 전부 저장하지 않고, 우유의 위치만 list로 저장해줬다. 해당 리스트를 탐색하며 우유에 방문처리하면서 진행한다. 함수가 실행될 때 현재 위치와 집의 위치의 거리를 계산하여 남아있는 체력으로 돌아올 수 있다면 답을 갱신해줬다. 메모리: 15160KB시간: 528ms언어: Java 11import java.io.*;import java... 2024. 7. 19. [백준] 20917: 사회적 거리 두기 https://www.acmicpc.net/problem/20917 풀이솔브드에 랜덤 마라톤 기능이 생겼다. 일주일마다 8문제를 랜덤으로 골라주는데, 풀 문제를 따로 고르지 않아 편한 점이 있다. 이 문제도 랜덤 마라톤에 있는 문제였다. 좌석들의 위치가 주어지고, 좌석을 s개 선택할 때 거리의 최댓값을 구해야한다. 좌석들의 위치를 입력받아 정렬했다. 서로 떨어진 거리를 기준으로 이분탐색을 하는데, 이때 일정 거리(mid)를 기준으로 좌석의 위치 배열을 앞에서부터 탐색하면서 배치할 수 있는 좌석의 개수를 헤아린다. 좌석의 개수가 원하는 개수보다 적다면 `high`를 `mid -1`로 배치하고, 원하는 개수 이상이라면 `mid`값을 `result`에 넣고, `low`를 `mid +1`로 늘려 더 큰 거리에서.. 2024. 7. 18. [백준] 17845: 수강 과목 - JAVA https://www.acmicpc.net/problem/17845 풀이과목들의 공부시간과 중요도가 주어진다. 자신의 한계 공부 시간을 넘지 않으면서 중요도의 합이 최대가 되도록 과목들을 선택해야 한다. 문제를 보자마자 배낭 문제라고 떠올랐다. 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 무게의 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 하는 배낭 문제에서 말만 바꾼 문제였다. 과목들의 정보를 배열에 담고, 최대 n의 시간에 맞춰 과목들을 dp배열에 담았다. 메모리: memoryKB시간: speedms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] .. 2024. 7. 18. 이전 1 2 3 4 ··· 25 다음