김머성 블로그

[BAE/<JOON> 문제풀이] 2031. 이 쿠키 달지 않아!

https://www.acmicpc.net/problem/2031 2031번: 이 쿠키 달지 않아! 첫 번째 줄에 4개의 자연수 T, N, D, K가 주어집니다. (1 ≤ T ≤ 109, 1 ≤ N ≤ 106, 1 ≤ D ≤ 109, 1 ≤ K ≤ 10) 두 번째 줄에 N 종류의 음식 각각을 먹을 시각을 나타내는 N 개의 자연수 a1, ..., aN이 주어집 www.acmicpc.net 서론 주어진 각 시간마다 차의 효능이 유지되는 구간을 미리 계산해 시간을 줄이는 문제 풀이 각 음식마다 차의 효능을 얻으면서 먹을 수 있는 구간이 정해져있다. 어떤 음식i 를 먹는 시간이 arr[i]라고 한다면 그 그 음식을 포함해 차의 효능을 얻을 수 있는 구간은 arr[i] - d + 1 분까지 이다. 시간을 정렬하고..

[BAE/<JOON> 문제풀이] 19236. 청소년 상어

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 서론 구현 문제. 고려해야할 인자들이 많아서 상당히 헷갈린다. 나도 여러 인자들이 꼬여있는 로직에서 틀린걸 못찾아서 3시간을 헤맸다. 풀이 그냥 문제에 있는걸 그대로 코드로 옮기면 된다. 그래서 풀이를 쓸 게 없다. 개인적으로 느낀 점은 알고리즘 문제 풀 때 본인만의 코딩 규칙을 만들고 지키는게 상당히 중요할 것 같다. 이 문제에서 좌표를 나타내는 구조체에는 x, y로 선언을 해..

[BAE/<JOON> 문제풀이] 2300. 기지국

https://www.acmicpc.net/problem/2300 2300번: 기지국 첫째 줄에는 건물의 개수 N이 주어지고 (1 ≤ N ≤ 10,000), 그 다음 N개의 줄에는 한 줄에 한 건물의 x-좌표와 y-좌표가 빈 칸을 사이에 두고 차례로 주어진다. x-좌표와 y-좌표는 절댓값이 1,000,000 이 www.acmicpc.net 서론 쓸게 딱히 없다. 정올 기출 치곤 쉬운 것 같다. 요즘 문제 표기난이도랑 실제 체감 난이도랑 너무 안맞아서 그냥 아무거나 풀고 있다. 풀이 라인 스윕이 부가적으로 들어가있다. 건물들을 x축 기준으로 정렬해놓고 건물들을 순차적으로 추가해나가며 최적값을 계산했다. 점화식은 아래와 같다. 현재 건물 i부터 이전 건물 j 사이의 모든 건물을 포함하는 정사각형의 크기는 m..

[BAE/<JOON> 문제풀이] 1727. 커플 만들기

https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net 서론 코너 케이스 만들기 그나마 편한 문제였다. 작은 입력으로 코너 케이스가 구현된다는 것 자체가 감사하다. 풀이 커플부터 최대한 많이 만들어야 하므로 커플 쌍은 반드시 min(남자 수, 여자 수) 가 된다. 또한 각 성별 성격수치를 오름차순 정렬하면 남녀를 대응시킬 때 순차적으로 대응시켜도 반례가 발생하지 않는다. 왜냐하면 차이의 합이라는건 남자 군집 a의 합과 여자 군집 b의 합의 ..

[BAE/<JOON> 문제풀이] 2253. 점프

https://www.acmicpc.net/problem/2253 2253번: 점프 N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 www.acmicpc.net 서론 특이하게 메모리 제한을 빡세게 걸어놨다. short 으로 하고 dp배열 계산식으로 할당해야 피해짐. 무식하게 10e7개 int 잡으면 안됨 풀이 현재 지점 i까지 올 수 있는 구간은 i / 2 ~ i - 1 까지다. i / 2 미만 지점에서는 점프거리를 늘리기만 해도 i에 닿을 수 없다. 마찬가지로 i에서 점프할 수 있는 최대 거리도 i다. 그 이상은 이전 단계에서 점프거리..

[BAE/<JOON> 문제풀이] 1720. 타일 코드

https://www.acmicpc.net/problem/1720 1720번: 타일 코드 2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다. 그런데 문제가 www.acmicpc.net 서론 타일 시리즈 가면 갈수록 어려워지는 것 같다. 지금 4 x n 시리즈랑 14 x 14 판때기 채우는거 2개 남았는데 왜 비트마스킹인지 아직도 모르겠다. 이것도 골드4인데 너무 안풀렸다. 풀이 수많은 삽질이 있었지만 정답 풀이만 쓰겠다. 이 풀이의 점화식이나 아이디어도 최적이 아닌 것 같긴 하다. 풀이 유도 과정은 아래와 같다. 해결했을 때 생각 과정을 그대로 순서대로 적었다. 단계 ..