SH

[백준 25969] 현대 모비스 자율 주행 시스템 - JAVA

https://www.acmicpc.net/problem/25969 그리디한 방법은 없으므로 완전 탐색을 한다.맵이 200 * 200 크기이므로, 재귀를 통한 DFS는 아마 시간초과가 날 것 같다.대신, BFS를 통해 dis(주행 거리)가 낮은 순으로 탐색하면 처음 도착했을 때 최단 거리임이 보장된다. 고려 사항[중간 지점의 방문 여부 / 패턴 사용횟수 k]에 따라 더 많은 dis를 주행했더라도 최적해일 수 있다.따라서, vst[N][M][K+1][2] 배열로 기록한다. r, c, k, vstMid가 같은데도 더 많은 dis를 주행했다면 이를 가지치기하며 탐색한다. 모호한 조건한번의 패턴 사용으로 총 n칸을 이동했더라도, dis를 1만 사용한 것으로 가정한다. (문제에 명시x 예제로 유추해야 함)impo..

[백준 31091] 거짓말 - JAVA

https://www.acmicpc.net/problem/31091 애드 혹 문제다.문제에 대한 이해(명제), 이상/이하 조건 분리, O(N^2)미만의 접근 모두 어려웠다.  누적합으로 해당 배열을 기록한다.p[i] : 거짓말을 한 사람이 i명이라고 가정했을 때, 조건( k명 이상이다)을 만족하는 사람의 수m[i] : 거짓말을 한 사람이 i명이라고 가정했을 때, 조건( k명 이하이다)을 만족하는 사람의 수  n명 이상이 거짓말을 하고 있다면,  0~n-1명 이상이 거짓말을 하고 있다는 명제도 참이다.p[n] = p[0~n-1] + p[n] n명 이하가 거짓말을 하고 있다면,  N~n+1명 이하가 거짓말을 하고 있다는 명제도 참이다.m[n] = m[N~n+1] + m[n] import java.io.Buf..

[백준 13305] 주유소 - JAVA

https://www.acmicpc.net/problem/13305 그리디 문제다. 현재 도시의 기름 값을 기준으로, 기름 값이 더 싼 도시를 찾을 때 까지 달린다. 더 싼 도시를 찾았다면, 그 도시의 기름 값을 기준으로 앞선 과정을 반복한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

[백준 25970] 현대 모비스 에어 서스펜션 - JAVA

https://www.acmicpc.net/problem/25970 완전 탐색을 해야함은 자명하다. Java로 생각한 방법 중 최고 복잡도가 나오는 (부분문자열 기반, 출력 최적화x)로 풀었는데 통과되었다. 아마 "특정 언어에서 쉬운 문제"가 아닌가 싶다. 정해(문제 분류)는 비트마스킹을 활용한 풀이다. (판단데이터 B (B.length  난이도 기여에 가면 좀 더 어려운 알고리즘을 적용할 수 있다고 써있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main { public static void main(String[] args) throws IOException { ..

[백준 26091] 현대모비스 소프트웨어 아카데미 - JAVA

https://www.acmicpc.net/problem/26091 입력을 오름차순 정렬한다. l = 현재 최소값 포인터, r = 현재 최대값 포인터로 정의한다. l+r >= M 이라면, ans++하고 다음 비교 (l++, r--) 로 넘어간다. l+r  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffere..

https://www.acmicpc.net/problem/2698 배열크기 & 한번의 탐색 복잡도 = 100(N) * 2(0 or 1) * 100(K) = 2만전체 복잡도 = 1000(TC) * 2만 = 2천만 dp[n][2][k] = n번째 자리에 0 or 1로 도달했을 때 인접 비트가 k인 경우의 수 n번째 자리가 0이면[n-1번째 자리가 0], [n-1번째 자리가 1]인 경우에서 k가 변하지 않는다. n번째 자리가 1이면[n-1번째 자리가 0]인 경우 k가 변하지 않는다.[n-1번째 자리가 1]인 경우 k가 1 증가한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java..

BOJ Linkhttps://www.acmicpc.net/problem/18869   풀이 과정1. 아래 조건을 만족해야 한다.Ai  → Bi Ai = Aj → Bi = BjAi > Aj → Bi > Bj=> 우선, 배열 A와 B를 value에 따라 정렬 했을 때, idx 순서가 같으면 된다. 2. 위 로직만 적용했을 때의 반례A = [1, 1, 1]B = [1, 1, 2]  오름차순 정렬을 했을 때, 둘 다 idx는 [0, 1, 2] 이다.그러나, A1 = 1, A2 = 1, B1 = 1, B2 = 2 이기 때문에 A1 = A2B1 꼴이 되어 조건을 만족하지 않는다.=> 따라서, rank를 부여하고 idx와 같이 비교한다. 3. 복기문제를 풀고나서 알았는데, 이는 좌표압축 기법을 사용하는 문제였다.차이..

BOJ Linkhttps://www.acmicpc.net/problem/1965     풀이 과정관심사는 최대 상자의 개수이다. 어떤 상자들로 최대를 만들었는지는 상관이 없다. 따라서,when cost[i] > cost[0~i-1] 일 때,dp[i] = (dp[0 ~ i-1] 중 최대 값) +1(i번째 상자 포함)로 놓았다. 이는 2중 for문으로 구현 가능하다.  제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;class Main { public static void main(String[] args) throws IOException..

BOJ Linkhttps://www.acmicpc.net/problem/1679   풀이 과정DP + 그래프 탐색 문제 어떤 수를 만들 수 있는지 판별보다, 만들 수 있는 모든 수를 기록해 놓는게 빠르다.그래프 탐색을 통해 "DP[만들 수 있는 수] = 도달한 depth" 를 적는다. 같거나 더 많은 depth로 도달했다면 가지치기 한다. 제출 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;class Main { static int N, K, num[], MAX, DEFAULT; static int[] vst; public sta..

BOJ Linkhttps://www.acmicpc.net/problem/1622   풀이 과정1.  a의 부분 수열의 순열이자 b의 부분 수열의 순열이 되는 가장 긴 문자열 x의 사전 순으로 가장 앞에 오는 것을 출력? 한마디로 a와 b가 공통으로 가진 원소 집합을 찾아 정렬하면 된다. map으로 a와 b의 를 저장한 뒤 공통 원소만 뽑는다.둘 다 어떤 원소를 가지고 있다면, 둘 중 더 적은 개수가 공통 원소가 된다. 2. 입력에는 빈 문자열이 올 수 있으며, EOF 처리를 해야함 전자의 조건은 놀랍게도 명시되어 있지 않다. 유추해서 처리해야 한다.if ("".equals(A) || "".equals(B)) { System.out.println(); continue;}while ((A = br..