김머성 블로그

[BAE/<JOON> 문제풀이] 11952. 좀비

https://www.acmicpc.net/problem/11952 11952번: 좀비 첫 번째 줄에 N, M, K, S가 공백으로 구분되어 입력된다. 각 값은 도시의 수, 길의 수, 좀비에게 점령당한 도시의 수, 위험한 도시의 범위 를 의미한다. (2 ≦ N ≦ 100000, 1 ≦ M ≦ 200000, 0 ≦ K ≦ N - 2, www.acmicpc.net 서론 그래프 문제여도 최적화에 대한 아이디어가 들어가 있어서 풀이를 작성했다. 풀이 핵심은 해처리로부터의 거리가 s 이상인 정점들을 효율적으로 구분하는 것이다. 당연히 정점을 방문할 때마다 거리가 s이하인 점들을 순회하면 TLE 가 난다. 토마토 문제를 풀 때 처럼 모든 해처리 위치를 큐에 집어넣고 각 해처리마다 거리가 s 인 점들을 모두 위험하다..

[BAE/<JOON> 문제풀이] 1036. 36진수

https://www.acmicpc.net/problem/1036 1036번: 36진수 첫째 줄에 수의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. N은 최대 50이고, 수의 길이도 최대 50이다. 마지막 줄에 K가 주어진다. K는 36보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 서론 문제가 마음에 든다. 요즘 구현 문제들이 재밌는 것 같다. 풀이 큰 수 연산 + 높은 진수 표현 문제다. 파이썬으로 풀면 편하지만 낭만이 없다. 1. 숫자가 36개 있으므로 각 숫자들이 각 자릿수에서 나타난 횟수를 저장한다. 2. 어떤 숫자가 Z ( 35 ) 로 바뀌면 35-숫자 만큼 추가되는 것이므로 Z로 바꿨을 때 얻을 수 있는 추가 합은 (36 - 숫자) * pow(10, 자리..

[BAE/<JOON> 문제풀이] 4457. 상근이의 자물쇠

https://www.acmicpc.net/problem/4457 4457번: 상근이의 자물쇠 상근이는 학교 사물함에 매우 비싼 물건을 보관한다. 이렇게 중요한 물건을 학교에 보관하는 이유와 무엇이 그렇게 중요한지는 아직 알려지지 않았다. 하지만, 상근이는 보안을 유지하기 위해 www.acmicpc.net 서론 구현 거지같이해서 무한 맞왜틀했는데 알고리즘 톡방에서 고수분(개잘함)에게 코드 리뷰받고 풀었다. 감사합니다. ㅠㅠ 잘하는 사람들 코드보고 반례찾는거보면 진짜 신기하다. 심지어 내가 맞다고 확신한 부분에서 틀렸는데도 끝까지 전수검사해서 찾아주심. https://anz1217.tistory.com/

[BAE/<JOON> 문제풀이] 24887. 최대한의 휴식

https://www.acmicpc.net/problem/24887 24887번: 최대한의 휴식 Amel은 SKH 회사 내에서 일을 잘하기로 소문난 유능한 사원이다. 그러나, 체력이 매우 안 좋은 Amel은 하루 동안 일하고 나면 빠르게 지쳐버리기 때문에 한 번 일하고 난 후 가능한 오랜 기간 동안 www.acmicpc.net 서론 파라메트릭 서치 문제. 최솟값의 최댓값이라는 워딩으로 빠르게 알아차릴 수 있었다. 풀이 구간의 쉬는 값 k를 이분탐색하면서 전체 배열에 대해 가능한지 여부를 검사한다. 탐색 인자 k 이상 건너뛰면서 주어진 일의 총량을 진행할 수 있는지 여부를 검사한다. k + 1 칸 이전에서 얻은 최대 일의 총량과 바로 이전 칸에서 얻은 일의 총량을 비교해서 더 큰 값으로 갱신하며 배열의 끝..

[BAE/<JOON> 문제풀이] 14948. 군대탈출하기

https://www.acmicpc.net/problem/14948 14948번: 군대탈출하기 첫 줄에 각 병영의 세로 길이 n, 가로 길이 m 이 주어진다. (1 ≤ n, m ≤ 100) 다음 줄부터 차례대로 병영의 블록별 레벨 제한 k가 주어진다. (0 ≤ k ≤ 109). www.acmicpc.net 서론 매우 일반적인 최단거리 문제 풀이 문제에서 '타일을 건너뛰어 다음 타일로 갈 수 있다.' 라고 써놔서 말 그대로 1칸만 뛰어넘는다는 소린 줄 알았는데 체스 룩 처럼 거리 제한 없는 점프였다. 나처럼 읽는 사람 있을 것 같은데 이것만 좀 신경쓰면 특별할 것 없는 최단거리 문제다. 4방향 일반이동, 4방향 점프이동 총 8가지 이동을 구현하고 각 지점마다 점프를 해서 온 최댓값 과 점프를 사용하지 않고..

[BAE/<JOON> 문제풀이] 2091. 동전

https://www.acmicpc.net/problem/2091 2091번: 동전 첫째 줄에 답을 출력한다. cent의 수, nickel의 수, dime의 수, quarter의 수를 출력한다. 불가능한 경우에는 0을 네 개 출력한다. www.acmicpc.net 서론 평범한 동전문제. DP 로 풀었다. 동전이 모두 배수 관계지만 특정 동전의 개수가 0일 경우 배수 관계가 성립하지 않을 수 있어 그리디 풀이는 배제했다. ( 10, 25 동전만 있는 경우 ) 풀이 점화식 DP[i][j] = i 번째 동전까지만 사용해 j원을 만들 때 최대 동전 사용 횟수와 각 동전을 쓴 횟수 ( [1~4]까지 동전, [0]은 총 횟수 ) DP[i][j] = max(DP[i - 1][[j - 현재 동전 가치][0] + 1, ..