본문 바로가기

Algorithm221

[백준] 1062: 가르침 - JAVA https://www.acmicpc.net/problem/1062 풀이배운 알파벳을 체크하기 위해 비트마스킹을 이용했다. 알파벳은 26자인데 int자료형은 2의 31제곱까지 표현이 가능하므로 비트마스킹을 적용할 수 있다. a, n, t, i, c 5개 문자를 -97 해서 숫자로 바꾼 뒤 체크해주었다. K개의 글자를 배울 수 있으므로 조합을 통해 K개를 채워주었다. K개가 되었다면 주어진 단어 중 읽을 수 있는 단어를 카운트해줬다.  메모리: 15216KB시간: 300ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int N, K, ans; static String[] arr; public static .. 2024. 5. 18.
[백준] 2169: 로봇 조종하기 - JAVA https://www.acmicpc.net/problem/2169 풀이`(0, 0)`에서 `(N-1, M-1)`까지 각 칸의 값을 더하면서 가는데 최댓값을 구해야한다. 이동은 아래, 왼쪽, 오른쪽으로 이동할 수 있다. 첫번째 줄에서는 오른쪽으로 이동할 수 밖에 없다. 첫번째 줄의 dp를 먼저 채우고 아랫줄로 내려간다. 두번째 줄부터는 왼쪽, 오른쪽 모두 이동할 수 있다. 오른쪽으로 가는 경우, 왼쪽으로 가는 경우를 나눠 tmp라는 배열에 저장한다. 이때 위에서 내려오는 값과 바로 옆 칸에서 오는 값을 비교하여 저장한다. 오른쪽, 왼쪽 경우를 비교하여 dp배열에 채운다. `dp[N-1][M-1]`을 출력하면 끝.  메모리: 79660KB시간: 608ms언어: Java 11import java.util.*;.. 2024. 5. 18.
[백준] 20160: 야쿠르트 아줌마 야쿠르트 주세요 - JAVA https://www.acmicpc.net/problem/20160 풀이야쿠르트 아줌마의 판매 경로 10개가 주어진다. 아줌마가 해당 위치에 도착하기 전에 가있어야 아쿠르트를 살 수 있다. 먼저 내 시작위치로부터 각 위치까지 얼마나 걸리는지 다익스트라를 통해 구했다. 야쿠르트 아줌마의 시간을 누적해가면서 경로대로 움직였다. 아줌마의 현재위치부터 다익스트라를 통해 다음 위치까지 시간을 구했고, 해당 시간이 `Integer.MAX_VALUE`이면 그 다음 위치를 보는 식으로 구현했다. `ans`를 갱신하여 정점의 번호가 가장 낮은 것이 정답.  메모리: 68732KB시간: 920ms언어: Java 11import java.util.*;import java.io.*;public class Main { s.. 2024. 5. 18.
[백준] 2637: 장난감 조립 - JAVA https://www.acmicpc.net/problem/2637 풀이X, Y, K가 주어지는데 X를 만드는데 부품 Y가 K개 필요하다는 뜻이다. 다른 부품으로 만들어지지 않는 기본 부품이 몇개씩 필요한지 구하는 문제이다. 완제품의 번호는 N으로 주어져있다. 따라서, N부터 탐색하면 된다. 위상정렬을 이용했는데 X를 만드는데 Y가 필요하다면 Y의 위상정렬 배열에 +1해줬다. N부터 시작하여 연결된 부품의 위상을 빼가면서 0이 되면 큐에 추가하는 식으로 구현했다.  메모리: 15960KB시간: 148ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int from; i.. 2024. 5. 17.
[백준] 15817: 배수 공사 - JAVA https://www.acmicpc.net/problem/15817 풀이파이프의 길이와 각 길이 파이프들의 개수가 주어진다. 이 파이프들을 갖고 x길이를 만드는 문제이다. 길이가 짧은것부터 주어지므로 따로 정렬할 필요는 없었다. 길이가 짧은 파이프부터 보면서 x부터 0으로 내려가면서 역순 탐색을 통해 dp배열에 값을 누적시켰다.  메모리: 14324KB시간: 232ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Pipe { int length; int count; public Pipe(int length, int count) { this.leng.. 2024. 5. 17.
[프로그래머스] 블록 이동하기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이두 점의 좌표, 방향, 시간을 Node클래스에 담아서 진행했다. 방문처리는 가로를 0, 세로를 1로 놓고 3차원 배열로 처리했다. 이동했을 때 두 점이 모두 방문한 곳이라면 진행시키지 않았다. 귀찮은 구현문제였다.  메모리: 69MB시간: 5.70ms언어: Java 11import java.util.*;class Solution { static class Node { int x1.. 2024. 5. 17.
[백준] 19598: 최소 회의실 개수 - JAVA https://www.acmicpc.net/problem/19598 풀이회의의 시작, 종료 시간이 주어지고 최의실을 배정해야 한다. 회의실의 개수를 최소로 해야한다. 시작시간 순으로 정렬을해서 차례대로 회의실에 집어넣었다. 우선순위큐에 종료시간을 넣고, 우선순위큐의 peek이 새로 들어갈 회의의 시작시간보다 작다면 그 방을 사용할 수 있다.  메모리: 48764KB시간: 668ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2024. 5. 17.
[백준] 13335: 트럭 - JAVA https://www.acmicpc.net/problem/13335 풀이n개의 트럭이 길지 w의 다리를 건너는데 1을 가는데 1의 시간이 소요되고 다리가 견딜 수 있는 무게는 L이다. 다리 위에 L넘게 올라갈 수없다. 먼저 간 트럭이 다리를 벗어날 때까지 기다려야한다. 큐에 다리위에 있는 트럭들을 저장하고 sum에 트럭의 무게를 더해줬다. 큐에 넣을 때 다리를 벗어나는 시간까지 같이 넣어주었다. 시간을 늘리면서 큐의 맨 앞에 있는 트럭이 다리를 벗어날 시간이라면 큐에서 삭제, sum에서 무게를 빼주었다. `sum + 다음에 들어올 트럭의 무게`가 L보다 작거나 같으면 큐에 트럭을 넣어주었다.  메모리: 14444KB시간: 136ms언어: Java 11import java.util.*;import java.. 2024. 5. 17.
[백준] 15810: 풍선 공장 - JAVA https://www.acmicpc.net/problem/15810 풀이만들어야 할 풍선의 개수와 한 사람이 풍선 하나를 만드는데 얼마나 걸리는지가 주어진다. 만들어야 할 풍선의 개수가 1,000,000개까지 주어지므로 연산과정에서 타입으로 long을 선택했다. 걸리는 시간을 기준으로 이분탐색을 진행했다. `left`는 1로, `righ`t는 (`소요 시간 배열의 최댓값 \* 풍선 목표량`) 으로 했다. `(left + right) / 2` 의 시간동안 각각 몇개씩 풍선을 만들 수 있는지 계산하여 더해줬고, 목표량보다 적으면 `left`를 `mid + 1`로, 크거나 같으면 `right`를 `mid - 1`로 해줬다. 계산값이 목표량보다 크거나 같을 경우 답을 갱신해줬다.  메모리: 93420KB시간: .. 2024. 5. 17.
[백준] 24337: 가희와 탑 - JAVA https://www.acmicpc.net/problem/24337 풀이a와 b중 큰 값을 먼저 놓고 왼쪽, 오른쪽에 다른 건물들을 배치하면 된다. a = 3, b = 5 라고 주어졌다면 5를 먼저 가운데에 세우고 왼쪽에 1 2, 오른쪽에 4 3 2 1을 배치한다. 즉, 1 2 5 4 3 2 1 과 같이 된다. 그 후 건물의 개수 N을 맞춰줘야 하는데 모자란 개수를 첫번째 건물을 세운 뒤에 1로 채워넣는다. 2번위치에 채우는이유는 첫 건물이 2 이상일 경우 앞에 1을 놓으면 a가 달라지기 때문이다.  메모리: 28116KB시간: 272ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(.. 2024. 5. 17.

티스토리툴바