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..