백트래킹16 [백준] 20208: 진우의 민트초코우유 - JAVA https://www.acmicpc.net/problem/20208 풀이집의 위치와 우유의 위치가 주어진다. 체력이 0이 되면 이동을 할 수 없다. 우유를 먹으면 일정 체력이 회복되는데 최대한 많은 우유를 먹고 집으로 돌아와야 한다. 처음에는 dfs로 풀이를 했는데 시간초과가 발생했다. 문제의 조건을 다시 보니 우유의 개수가 10개를 넘지 않는다는 것을 확인했다. 지도를 전부 저장하지 않고, 우유의 위치만 list로 저장해줬다. 해당 리스트를 탐색하며 우유에 방문처리하면서 진행한다. 함수가 실행될 때 현재 위치와 집의 위치의 거리를 계산하여 남아있는 체력으로 돌아올 수 있다면 답을 갱신해줬다. 메모리: 15160KB시간: 528ms언어: Java 11import java.io.*;import java... 2024. 7. 19. [백준] 19942: 다이어트 - JAVA https://www.acmicpc.net/problem/19942 풀이각 재료별로 단백질, 지방, 탄수화물, 비타민 함유량과 가격이 주어진다. 재료들을 혼합하여 영양분들을 더해 최소 영양분을 충족해야 한다.(최소 금액으로) 부분집합을 만들어 만들어진 집합에 대해 영양분들의 합이 만족하는지 판별해주었다. 비용이 이전의 비용보다 적은 경우에 갱신해주었고, 재료들의 번호를 출력해야 했기에 `TreeSet` 을 선언하여 담았다. 이전의 최소 비용과 같은 경우에는 TreeSet에 추가만 해주었고, 이전 최소 비용보다 작은 값이여서 갱신이 필요한 경우엔 TreeSet을 새로 선언하여 추가하였다. TreeSet은 사전 순으로 정렬되기 때문에 TreeSet의 `first()` 메소드를 이용해 답을 출력했다. 메모리.. 2024. 5. 19. [백준] 16987: 계란으로 계란치기 - JAVA https://www.acmicpc.net/problem/16987 풀이계란마다 내구도, 무게가 주어진다. 계란끼리 부딪혔을 때 내구도는 상대 계란의 무게만큼 깎이는데, 내구도가 0이하가 되면 계란이 깨진다. 계란을 최대 몇개 깰 수 있는지 구해야 한다. dfs를 통해 1번 계란 부터 진행했다. idx번 계란을 어떤 계란과 부딪혔을 때 계란들의 내구도와 깨진 개수를 갱신해 idx+1번으로 넘어가 진행한다. 반복문을 통해 해당 계란이 여러 번호의 계란과 부딪히는 것을 시뮬레이션해볼 수 있도록 부딪힌 후에 결과를 초기화 해주는 과정이 필요했다. 메모리: 15708KB시간: 232ms언어: Java 11import java.io.*;import java.util.*;public class Main { .. 2024. 5. 19. [백준] 1497: 기타콘서트 - JAVA https://www.acmicpc.net/problem/1497 풀이처음에는 기타마다 연주할 수 있는 곡을 비트마스킹으로 체크하려고 했으나 곡의 개수가 최대 50까지 되기 때문에 int범위에서 비트마스킹을 할 수 없었다. 따라서 boolean 이차원 배열을 만들어 체크했다. N개의 기타로 만들 수 있는 조합을 모두 만들어 연주할 수 있는 곡을 체크해줬다. 비트마스킹을 사용하려고 했던 것이 아쉬워 조합을 만들 때 비트마스킹을 이용했다.for (int i = 1; i 1부터 2의 N제곱까지의 자연수 중 비트의 자리수가 1인 것이 선택된 기타이다. 메모리: 14548KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { .. 2024. 5. 18. [백준] 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. [백준] 1189: 컴백홈 - JAVA https://www.acmicpc.net/problem/1189 풀이(R-1, 0)에서 (0, C-1)로 이동한다. T는 가지 못하는 부분이고, 한번 지나친 곳은 다시 방문하지 않는다. 이동거리가 K인 경우의 수를 구하는 문제이다. 따라서 방문처리를 하며 dfs탐색을 했다. 각각의 경우에 따른 방문처리가 서로 영향을 주어서는 안되기 때문이다. 이동 거리를 1씩 늘려가면서 다음 칸으로 이동했고, 이동 거리가 K가 됐을 때, 도착점에 도달하였을 때 사이클을 종료시켰다. 메모리: 14584KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[][] vector = { { 1, 0 }, { 0, 1.. 2024. 5. 17. [백준] 7490: 0 만들기 - JAVA https://www.acmicpc.net/problem/7490 풀이1부터 N까지의 수 사이에 +, -, 공백을 넣어서 수식을 만들고 그 수식을 계산하여 0이 되는 경우 출력해야 한다. 출력할 때 ASCII 순서에 따라 출력하라는 제한이 있어서 공백, +, - 순서로 dfs탐색을 통해 수식을 만들었다. N까지 진행하면 수식을 계산하는 메서드를 통해 0이 나오면 값을 출력한다. 메모리: 17200KB시간: 168ms언어: Java 11import java.io.*;public class Main { static int N; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws.. 2024. 5. 17. [백준] 17255: N으로 만들기 - JAVA https://www.acmicpc.net/problem/17255 풀이어떤 수 N을 만들어야 하는데 두 가지 행동을 반복해서 만들어야 한다. 1. 수의 왼쪽에 숫자를 하나 적는다. 2. 수의 오른쪽에 숫자를 하나 적는다. 따라서, 숫자 N을 입력받을때 char 배열로 받아서 인덱스로 탐색하면서 시작위치를 정하고 dfs탐색을 했다. left와 right 인덱스를 기억하면서 left가 0, right가 길이-1이 되면 set자료구조에 넣었다. 나온 수를 순서대로 string으로 만들어 set자료구조에 넣었기 때문에 중복된 것이 제외되고 set의 size를 출력하면 경우의 수가 된다. 메모리: 17296KB시간: 216ms언어: Java 11import java.util.*;import java.io.*;.. 2024. 5. 17. [백준] 15683: 감시 - JAVA https://www.acmicpc.net/problem/15683 풀이cctv의 방향을 설정하여 사각지대를 최소로 만들어야 한다. cctv의 종류는 5가지가 있다. 2번 cctv는 방향을 선택할 수 있는 방법이 2가지, 5번 cctv는 1가지였다. 나머지 cctv는 4방향 모두 선택할 수 있다. 입력받으면서 cctv의 위치를 저장했고, 그들의 방향을 저장할 배열을 만들어 각각 어떤 방향을 선택할지 조합을 만들었다. 조합이 완성되면 그 방향에 맞게 빈칸을 채워가면서 체크했다. 처음에 빈칸(0)의 개수를 세어놓고 빈칸을 몇개나 채웠는지를 세어 빼주면 된다. 메모리: 72084KB시간: 304ms언어: Java 11import java.io.*;import java.util.*;public class M.. 2024. 5. 12. [백준] 15686: 치킨 배달 - JAVA https://www.acmicpc.net/problem/15686 풀이브루트포스, 백트래킹문제. 치킨집 중 M개를 골라 집들과의 거리를 구한 합의 최솟값을 구하는 문제. 치킨집과 집을 리스트에 넣고 치킨집중 M개의 조합을 만들었다. 만들어진 치킨집의 조합을 이용해 집과 치킨집 거리의 최솟값들의 합을 구해주었다. 메모리: 15112KB시간: 220ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int r; int c; public Node(int r, int c) { this.r = r; this.c = c; .. 2024. 5. 11. 이전 1 2 다음