동환아 공부해야지

[백준/Java] 2961: 도영이가 만든 맛있는 음식

문제: https://www.acmicpc.net/problem/2961 조건TimeLimit = 1s신맛 (S 사용한 재료들의 신맛 곱쓴맛 (B 사용한 재료들의 쓴맛 합재료 수 (1요리할 때, 재료는 적어도 한 개 이상 들어가야함신맛과 쓴맛의 차이가 가장 작은 요리에서, 차이는? 풀이완탐재료를 한 개 선택하는 경우부터, 10개 선택하는 경우까지 존재최악의 경우는 10개의 재료중 5개를 선택하는 경우임따라서 시간복잡도는 10(1개부터 10개까지 선택하는 경우) * 10C5(10개중 5개 선택하는 경우)-> 10*10C5 코드import java.util.*;import java.io.*;public class Main { static StringTokenizer st; static int n; ..

문제: https://www.acmicpc.net/problem/14888 조건TimeLimit = 2s사칙연산자만 존재 (차례대로 +, -, *, /)연산자 우선순위를 무시하고, 앞에서부터 차례대로 계산 진행식 결과중, 최댓값과 최솟값을 출력2 풀이백트래킹최대 4개의 선택지(사칙연산자) * 깊이(연산자 최대10개 존재)-> O(4**10) ~= O(100만)-> 시간복잡도 통과음수도 나올 수 있으므로, MinValue와 MaxValue 초기화를 잘해주자 코드import java.util.*;import java.io.*;public class Main { static StringTokenizer st; static int n; static int[] nums; static int[] ops; sta..

문제: https://www.acmicpc.net/problem/12101 조건TimeLimit = 1s11,2,3을 조합해서 n을 만들어야함가능한 조합의 오름차순에서 k번째를 출력 풀이완전탐색가능한 모든 값을 탐색하자 코드import java.util.*;import java.io.*;public class Main { static int n; static int k; static ArrayList cur; static ArrayList result; public static void main(String[] args) throws IOException { // input BufferedReader br = new BufferedReader(new InputStreamReader(Syste..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/389479?language=java 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 조건같은 시간대, 사람이 m명 늘어날 때마다 서버 1대 추가해야함, m명 미만이라면 필요x즉, n*m n대의 서버가 필요이용자수(players = 24), 1한번 증설한 서버는 k 시간 동안만 운영 (시작시간 ~ 시작시간+k)모든 게임 이용자가 게임을 하기 위해서, 서버를 최소 몇 번 증설해야 하는가? 풀이완전탐색시간당 서버 개수를 나타내는 int[] server와, 증설횟수 cnt를 다루자(server 배열의 값..

문제: https://www.acmicpc.net/problem/1012 조건TimeLimit = 1s가로길이(1섬찾기 문제 풀이BFS전형적인 섬찾기 문제이므로 BFS를 사용하자배추 위치가 없다면 모든 점에 대해 완탐을 진행해야하는데, 위치가 주어지므로 해당 값들을 start point로 탐색을 진행하자visited 배열을 사용하지 않고, 방문한 점에 대해서는 값을 +1 해주어서 방문체크를 진행한다이때 start point를 한번이라도 방문할 수 있다면 섬이라는 뜻이므로 count를 +1 해준다 코드import java.util.*;import java.io.*;public class Main { static BufferedReader br; static StringTokenizer st; stat..

문제: https://www.acmicpc.net/problem/2178 조건TimeLimit = 1sN,M 크기의 미로 (21은 이동가능, 0은 이동 불가능상,하,좌,우는 이동가능하지만, 대각선은 불가능(1,1) -> (N,M)까지 필요한 최소 칸 수를 구하라시작위치, 도착위치도 칸 수에 포함해야한다 풀이BFS최단거리를 구해야 하므로 BFS를 사용하자visited 배열을 사용한 방문처리와, count 변수를 사용한 이동 칸 갯수를 사용하지 않는다대신 다음을 사용하자"이동한 칸의 value = 이동전 칸의 value +1"이후 다음 조건에 의해 validate를 진행한다- 이동하려는 칸이 범위를 벗어나는가?- 이동하려는 칸이 시작점인가?- 이동하려는 칸이 0인가? (움직일 수 없는 곳)- 이동하려는 칸..

문제: https://www.acmicpc.net/problem/1260 조건TimeLimit = 2s정점 개수(1방문 가능한 정점이 여러개면 -> 작은 것부터 방문해야함DFS 방문 경로와 BFS 방문 경로를 차례대로 출력 풀이각 node에 연결된 node 집합을 준비해야함해당 집합들을 구한 후 sort해주자 DFS함수 실행시 먼저 방문처리이후 edge 연결할 때, visited 확인하여 연결된 node로 함수 재실행BFS처음 queue에 start node를 집어넣을 때, start node 방문처리이후 queue가 empty 될때까지 while문 반복wihle문 안에서는 queue의 제일 앞에있는 값을 뽑아냄이후 그 값으로 연결된 node를 탐색하며 방문한 node라면 continue방문하지 않..

문제: https://www.acmicpc.net/problem/16943 조건TimeLimit = 2s1A의 순서를 섞어서, B보다 작은 C를 만든다단, C는 0으로 시작하면 안된다C의 최댓값을 구하되, 조건을 만족하는 C가 없다면 -1을 출력하라 풀이완전탐색10자리 수를 섞는법 -> 10! ~= 360만. 즉, 완탐 가능A에서 중복되는 index만 없도록 순열을 구하자size = A size가 될때까지 반복하고, 이후 Integer.parseInteger로 비교하자visit 필요함첫 번째가 0이 안되도록 조건 추가할 것 코드import java.io.*;import java.util.*;public class Main { static StringTokenizer st; static String[]..

문제: https://www.acmicpc.net/problem/20950 조건TimeLimit = 1s물감개수(2문두리색 = 곰두리 색과 가장 차이가 작은 물감색물감색 차이 = |R1-R2| + |G1-G2| + |B1-B2|혼합 물감 RGB = 각 물감 RGB를 더한 후, 더한 갯수로 나눈다(소숫점 버림)문두리색과 곰두리색의 차이를 구하라 풀이완탐모든 물감중, 2개~7개를 선택하여 문두리색을 구해본다2개 구하는 경우(30C2), 3개 구하는 경우(30C3), ... 7개 구하는 경우(30C7)-> O(30C2 + 30C3 + ... + 30C7) -> 30C7 = (30*29*28*27*26*25*24)/(7*6*5*4*3*2) = (30*29*26*10*9) -> 따라서 시간복잡도 ~= O(6..

문제: https://www.acmicpc.net/problem/10819 조건TimeLimit = 1s3배열안의 숫자들 순서를 임의로 바꿨을 때, 다음 식을 만족하는 최댓값을 구하라|A[0]-A[1]| + |A[1]-A[2]| + ... + |A[n-2]-A[n-1]| 풀이완탐가능한 전체 배열 조합을 전부 확인하는 방법최대 n=8일때 가능한 모든 조합은 O(8!) = O(40,320) -> 완탐 가능index가 중복되지 않게 백트래킹을 진행하자 코드import java.io.*;import java.util.*;public class Main { static int n; static boolean[] visit; static int[] arr; static int[] curArr; static i..