동환아 공부해야지

문제: 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..

문제: https://www.acmicpc.net/problem/1182 조건TimeLimit = 2s1크기가 1 이상의 부분수열 중, 합이 S가 되어야 함 풀이백트래킹시작값을 바꿔가며 전체를 탐색해본다 코드import java.io.*;import java.util.*;public class Main { static StringTokenizer st; static int n; static int s; static int[] arr; static int cnt; public static void main(String[] args) throws IOException { // input BufferedReader br = new BufferedReader(new InputStreamReader(Sy..

문제: https://www.acmicpc.net/problem/14501 조건TimeLimit = 2s1 상담일 (1 풀이백트래킹1일차부터 N일차까지 시작일을 옮기면서 계산상담일이 N일 이상이라면 종료조건정확히 N일이면 현재 수익을 그대로 비교, N일보다 크다면 마지막 수익금을 빼고 비교 코드import java.io.*;import java.util.*;public class Main { static StringTokenizer st; static int n; static int[] t; static int[] p; static int maxP = 0; public static void main(String[] args) throws IOException { // input Buffered..

문제: https://www.acmicpc.net/problem/2529 조건TimeLimit = 1s2선택한 수에 중복 없도록숫자는 0~9 풀이백트래킹작은수부터 차례대로 최종까지 모두 진행해야함 (min, max 구할거라서)순서대로 진행하므로 비교할 필요는 없고, min은 한번만, max는 계속 갱신해야함 코드import java.io.*;import java.util.*;public class Main { static int n; static String[] signs; static boolean isFirst = true; static int[] minNums; static int[] maxNums; static boolean[] visit = new boolean[10]; public st..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/14718 조건TimeLimit = 1s병사 수 N, 이겨야 할 병사 수 K (1 진수가 이기는 조건 (아래를 모두 만족)- 진수 힘 >= 병사 힘- 진수 민첩 >= 병사 민첩- 진수 지능 >= 병사 지능 풀이완전탐색-> 각 스텟의 모든 조합을 구해본다-> 주어진 병사가 최대 100명이므로, 시간복잡도는 O(100*100*100)으로 충분히 통과-> 각 병사의 '힘', '민첩', '지능' 스텟을 배열로 저장하고, 오름차순 정렬시켜서 비교하자 코드더보기import java.io.*;import java.u..

문제: https://www.acmicpc.net/problem/23882 조건TimeLimit = 1s배열크기 (5 교환횟수 (1 풀이선택정렬을 구현하자-> 정렬을 진행할 사이즈를 제한하고, 가장 큰 수가 뒤로가도록 구현한다-> 한번 교환이 일어나면 사이즈를 줄인다-> for (last = n-1; last >=0; last --) // 최댓값 관련 정보 max = arr.max(0~last사이) max_idx = arr.index(max) // 교환 if (max_idx != last) last_v = arr[last]; arr[last] = max; ..

문제: https://www.acmicpc.net/problem/16171 조건TimeLimit = 1s1 풀이S의 문자열을 하나씩 탐색하여, 숫자를 제외한 새로운 S를 만든다-> 이때 아스키 코드를 사용해보자이후 S.contains(K)로 결과를 확인한다 코드더보기import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { // input BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] s_char = br.readLine().toChar..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/5883 조건TimeLimit = 1s사람 수 (1용량 (0 풀이B의 한 종류씩 전부를 빼면서 완전탐색을 하면?-> 최악의 경우, 1000종류의 B와, 1000명의 사람을 탐색-> 따라서 O(1000*1000) = O(100만) 이므로 충분함어떻게 구현?-> 종류는 중복을 없애기 위해서 Set로 다룬다-> '연속 구간 사이즈'는, 사람들의 요구 바이트 배열(bites)에서 하나의 type씩 제외한다음, 연속되면 +1 해준다-> Before와 Current를 선언해서 사용하고, 조건에 따라서 '연속 구간 ..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/2304 조건TimeLimit = 2s11지붕의 어떤 부분에도 오목한 부분이 존재하면 안된다 풀이오목한 부분이 없으려면 다음 조건에 따라 지붕을 이어야 한다-> 가장 높은기둥을 '기준'으로 삼는다-> '기준'으로부터 다음 좌/우 기둥들은, '기준'보다 높이가 같거나 작아야 한다-> 이후 '기준'을 다음 좌/우 기둥들로 변경한다-> 가장 마지막 기둥에 도달할 때까지 위를 반복한다이때 가장 높은기둥이 여러 개라면?-> 높이가 동일한 가장 높은기둥들 중, 가장 끝에 위치한 두 기둥 사이의 면적을 더해준다-> ..