동환아 공부해야지

문제: 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지붕의 어떤 부분에도 오목한 부분이 존재하면 안된다 풀이오목한 부분이 없으려면 다음 조건에 따라 지붕을 이어야 한다-> 가장 높은기둥을 '기준'으로 삼는다-> '기준'으로부터 다음 좌/우 기둥들은, '기준'보다 높이가 같거나 작아야 한다-> 이후 '기준'을 다음 좌/우 기둥들로 변경한다-> 가장 마지막 기둥에 도달할 때까지 위를 반복한다이때 가장 높은기둥이 여러 개라면?-> 높이가 동일한 가장 높은기둥들 중, 가장 끝에 위치한 두 기둥 사이의 면적을 더해준다-> ..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/2503 조건TimeLimit = 1sflow1. 영수가 숫자 생각2. 민혁이가 질문3. 질문에 대해 'n 스트라이크, m 볼' 로 대답4. 3 스트라이크 나올때까지 질문스트라이크 = 위치 & 숫자 모두 맞추는 경우, 볼 = 숫자는 맞지만 위치가 다른 경우1 풀이서로 다른 세자리수를 정렬시키는 방법의 수는 9P3 = 504가지-> 각 504개의 수에 대해, 모든 질문을 다 해봐도 N이 최대 100이므로 시간복잡도는 O(50400)-> 완탐 가능각 숫자에 대해 N개의 질문-> 하나라도 만족을 못한다면 co..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/1816 조건TimeLimit = 2s'매우 큰 소수' = 10**6보다 큰 소수S의 모든 소인수가 10**6보다 크면 적절하다110**12 풀이적절한지만 판단하면 됨 (몇 개가 나오는지가 아님)-> 즉, 각각의 S에 대해 '10**6보다 작은 소인수 여부'만 판단하면 되는 문제-> n이 최대 10이고, [1~10**6-1]중에 약수가 있는지 확인해야함-> 따라서 모든 S에 대해 [1~10**6-1]로 나누어보고, 나머지가 0이라면 'NO'를 출력-> n이 최대여도 O(10**7)로 충분히 만족 코드더..