Ikjo's Technology blog

문제 설명 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 회고 문제 이해하기 해당 문제는 '문제를 이해'하는데 많은 시간이 소요되었습니다. 😥 우선 문제에서 요구하는 것은 지민이가 과장된 이야기를 할 수 있는 파티의 수 즉, 진실을 아는 사람이 포함되어 있지 않는 파티의 수를 구하는 것입니다. 이때 중요한 점(놓치기 쉬운 점)은 최초 진실을 아는 사람이 포함되어 있는 파티에 다른 사람(최초 진실 구별 X)이 최초 진실을 아는 사람이 없는 다른 파티에 있더라도 지민이는 앞서 최초 진실을 아는 사람이 존재하기 때문에..

문제 설명 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 회고 제가 해당 문제를 풀기 위한 접근 방법은 다음과 같았습니다. 주어진 2차원 배열 상의 요소별 값(집터 좌표별 블록의 높이) 중 최솟값(최소 블록 높이)와 최댓값(최대 블록 높이)를 구한다. 최소 블록 높이부터 최대 블록 높이까지 각각의 값으로 블록의 높이를 모두 일정하게 바꾸고(땅 고르기) 이 경우의 소요 시간과 블록 높이를 구한다. 각각의 값으로 순차적으로 땅 고르기 작업을 할 때마다 낮은 시간을 우선적으로 산출하고 시간이 동일할 경우 더..

문제 설명 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 회고 제가 해당 문제를 풀기 위한 접근 방법은 다음과 같았습니다. 주어진 2차원 배열에 대해 임의의 3개의 벽 세우기 바이러스 확산시키기 안전 영역 크기 구하기(기존 값과 대소 비교 후 더 큰 값 할당) 변경된 2차원 배열 초기화하기 1번으로 돌아가 다시 임의의 3개의 벽 세우기(기존 3개의 벽과 완전히 중복되지 않는 3개의 벽) 위 단계에서 제가 가장 구현하기 까다로웠던 부분은 "임의의 3개의 벽을 세우는 것"이었습니다. 사실 DFS나 BFS를 통해 임의의 ..

문제 설명 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 회고 해당 문제에서 요구하는 것은 일자별로 주가가 주어졌을 때 주식을 샀다 팔았다(단타) 해서 낼 수 있는 최대 이익을 구하는 것입니다. 즉, 핵심은 쌀 때 사서 비쌀 때 파는 것입니다. 해당 문제에서 두고 있는 시간 제한은 5초로 다소 여유(?) 있다고 생각했었습니다. 그리하여 처음에는 단순 무식한 방법으로 2중 for문을 통해 문제에 접근했었습니다..😅 일자별 주식을 그 이후의 주식의 가격과 일일이 비교해보면서 가장 비싼 주식을 찾..

문제 설명 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 회고 : DFS와 BFS 차이에 대한 고찰 해당 문제에서는 체스판 위에 "나이트"의 "현재 위치"가 주어졌을 때 "특정(목표) 위치"로 갈 수 있는 최소 이동 횟수를 요구하고 있습니다. 즉 특정 지점에서 출발하여 "나이트의 이동 방식"에 맞춰 체스판(그래프) 위 각 좌표(노드)들을 탐색하면서 목표 위치를 찾아내야 합니다. 이때 최소 이동 횟수를 구해야 하므로 각 노드들을 이동할 때마다 이동 횟수를 1씩 더해주어야 합니다. 이러한 탐색 방법에는 DF..