dong_gas

오랜만에 문제풀이 글 지난 주, 학회 연습셋에 쓸 문제가 마땅치 않아 USACO 문제를 두 개 넣었었고, 그 중 하나이다. 나는 이 문제가 굉장히 까다롭다고 생각했다. 그리고 풀이 세션할 때 질문이 많이 들어올 줄 알고, 연습셋 때 풀이를 열심히 준비했었다. 근데, 다들 잘 풀더라... 질문도 없었다. 아쉬워서 글로 남겨본다. boj.kr/24979 문제를 요약하면 다음과 같다. C는 OW 혹은 WO로 바꿀 수 있다. O는 CW 혹은 WC로 바꿀 수 있다. W는 CO 혹은 OC로 바꿀 수 있다. 인접한 두 문자가 같으면 두 문자를 삭제할 수 있다. 이제 쿼리 [l, r]이 들어온다. 구간 [l, r]에 위 연산을 원하는만큼 적용해서 s[l..r]을 "C"로 만들 수 있는지 묻는 문제이다. 코드포스 같은 ..

오래간만에 쓰는 문제풀이 글. 오늘 999문제를 풀고 djs100201에게 1000문제 제물로 좋은 문제를 추천해달라고 했더니 추천해준 문제이다. 과제를 하기 싫기도 하고, 1000문제를 찍어서 기분이 좋기도 하고, 문제가 좋기도 하고 암튼 그래서 써본다. boj.kr/8479 문제 좋은 것 같아요. 추천합니다 ㅎㅎ! 이런 문제는 어떻게 만드는 건지...ㄷㄷ 우선 문제를 이해하기가 쉽지 않았다... 영어 지문임을 감안해도 좀 못 쓴 것 같다. 고릴라 컨셉을 넣어서 그런 것 같다. 암튼, 문제를 요약하면... Graph가 주어진다. 각 노드마다 사람의 수가 있다. 괴물은 매일 1번 노드에서 x번 노드에 가서 거기 있는 사람을 모두 먹는다. 이때, 1번 노드에서 x번 노드로 가는 길에 있는 사람들은 모두 죽..

2041번: 숫자채우기 N×M 크기의 격자에 적절히 수를 채우려 한다. 단, 인접한 수들의 차이로 1부터 (2NM-N-M)까지의 수가 한 번씩 나오도록 채우려 한다. N=2, M=2인 경우를 예로 들면 다음과 같은 방법이 있다. 위와 같 www.acmicpc.net 요즘 여기저기서 많이 보이는 문제이다. 다이아문제인데, 애드혹과 구성적 태그가 달려있길래 나도 도전해 보았다. 처음으로 푼 다이아 문제인데, 혼자 풀어내서 정말 행복하다 ㅎㅎ! 문제를 이해하는 것은 어렵지 않다. 인접한 원소의 차이가 1부터 2NM-N-M까지 모두 나오는 행렬을 만들면 된다. 두 개의 풀이가 있다. 첫 번째 풀이는 나의 풀이고 두 번째 풀이는 동기 meque98의 풀이이다. 두 풀이 모두 4칸씩 볼 때, 차이 2개를 정해주면 ..

99% 똑같은 문제다. 이 글은 2325 개코전쟁을 기준으로 서술하였다. 문제를 풀고, 글을 읽으면 좋을 것 같다. 2325번: 개코전쟁 “앙두레 강”이 개미와 코끼리 결혼식에서 기차를 아름답게 만드는 것을 실패했기 때문에 식장이 아수라장이 되고 결혼이 물거품이 되어버렸다. 급기야는 왕국 간에 분쟁으로 이어져 개미왕 www.acmicpc.net 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 문제를 요약해보자. 1번 -> N번으로 가는 최단거리가 최대가 되도록 길을 하나 없애야 한다. 그런 식으로 길을 하나 없앤 후..

신촌연합 중급반 연습문제로 풀다가 푼 문제. 1671번: 상어의 저녁식사 어떤 상어는 저녁식사로 서로를 먹는다. 모든 상어는 자신과 다른 상어의 크기, 속도, 지능을 수치로 나타낸 것을 알고 있다. 만약, 상어 A의 크기, 속도, 지능이 상어 B의 크기, 속도, 지능보다 크 www.acmicpc.net 문제 요약) N마리의 상어가 있다. N마리의 상어는 크기, 속도, 지능이 있다. 이 세 개 모두 다른 상어보다 크거나 같으면 다른 상어를 먹을 수 있다. 각 상어는 최대 2마리까지 먹을 수 있다. 남아있는 상어가 최소가 되게 먹었을 때, 남아있는 상어의 수는? 1. 상어가 다른 상어를 먹는다... 각 상어가 최대 2마리까지 먹을 수 있음... 최대한 많이 먹어야 함... 2. 이거 어디서 본 상황이다. 플..

오늘 학교에서 풀어서 맘에 드는 문제. 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 1. 크기가 짝수인 배열이 주어진다. (배열의 원소는 서로 다르다.) 남는 거 없이 2개씩 짝지어야 한다. 각 짝의 합은 소수가 되어야 한다. 2. 어떻게 두 개를 짝지을 수 있을까? 서로 다른 두 수를 더해서 소수가 되는 경우를 살펴보자. - 짝수끼리 더하면 무조건 짝수니까 소수가 나올 수 없다. - 홀수끼리 더하면 무조건 짝수니까 소수가 나올 수 없다. (1+1은 소수지..

2021/12/14에 올리는 글입니다. 10948번: Daily 로또 1보다 크거나 같고, 45보다 작거나 같은 수를 6개 출력한다. 이때, 같은 수를 여러 번 출력하면 안 된다. www.acmicpc.net 매일 아침 9시에 정답 번호가 바뀌는 문제이다. 어제 한 50번 시도하다가 20점 한 번을 못 받아서 포기했었다. 오늘은 71번의 시도 끝에 맞추었다. 20점을 받으면 매우 쉬워지는 문제이다. 내일이 시험시작이기 때문에 이 짓을 할 수 있었던 것 같다. 오늘의 번호는 다음과 같다. 5 12 15 17 24 45 참고로 보너스번호는 4이다. 내일 오전 9시 이전에 저 번호를 내시면 100점을 받으실 수 있습니다. 암튼 이제 시험공부를 시작할 예정이다. 내일 시험인 과목이지만 오늘 처음 공부한다. 그치..

23560번: 약 백준이는 $N$일 동안 약을 먹어야 한다. 약은 아침, 점심, 저녁에 한 번씩 먹어야 하고, 한 번 먹는 약은 약 봉투에 담겨있다. 약 봉투는 $3N$개가 일렬로 붙어 있고, {(아침 약), (점심 약), (저녁 약)} www.acmicpc.net 어렵지 않은 실버 dp 문제이다. 학회에 질문이 올라왔던 문제라 한 번 풀어보았다. 나는 dp로 풀었는데, 다른 동기는 등비수열 꼴의 매우 간단한 일반항으로 문제를 해결하였다. 신기해서 풀이를 써본다. 문제는 어렵지 않다. N일동안 아침, 점심, 저녁 약 봉투에서 약을 뜯어서 먹어야 한다. 이 때, 아침약과 저녁약은 똑같다. 약 봉투는 3N개가 일렬로 붙어 있고, {(아침 약), (점심 약), (저녁 약)}을 N번 이어붙인 형태이다. 약을 먹..

1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net DP문제였다. 나는 Top-Down으로 풀었다. 인터넷에 Top-Down으로 푼 사람이 별로 없고 과제하기도 싫어서(?) 글을 올려본다. 문제는 간단히 다음과 같다. 학기가 N일인 경우에 개근상을 받을 수 있는 출결정보의 개수를 세는 문제이다. 개근상을 받을 수 없는 사람은 지각을 두 번 이상 했거나, 결석을 세 번 연속으로 한 사람이다. 그 외의 모든 경우는 개근상을 받을 수 있다. 풀이 문제를 읽어보면 비교적 쉽게 DP인 것을 눈치챌 수 있다. 만약 학기가 N일차이면 N..

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 2021.11.05 기준 solved.ac 골드 5 Greedy 문제이다. 이 문제는 지문을 보고 문제를 이해하는 것이 쉽지 않았다. 국어를 못하긴 하지만.... 이런 내가 지문을 조금 더 이해하기 쉽게 바꿀 수 있겠다고 생각할 정도였으니..... 풀이 우선 문제는 대충 다음과 같다. 일직선의 고속도로에 N개의 센서가 있다. 센서가 수집한 자료를 분석할 집중국을 K개 세울 것이다. 이때, 모든 센서가 적어도 하나의 집중국의 범위에 있어야..