dong_gas

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

대학교에 입학하고 두 번째 방학이 끝났다. 지난 여름방학에 이어 이번에도 신촌 연합 알고리즘 캠프에 참가하였다! 여름 캠프 후기글 조회수가 잘 나오기도 했고, 이번에도 후기 글 이벤트를 한다길래 또 끄적여본다. 뭐 무엇보다도 캠프에서 많이 얻어갔으니까! [ICPC Sinchon] 2021 Summer Algorithm Camp 후기 링크! 주저리 주저리 https://icpc-sinchon.io/ Main | ICPC Sinchon 신촌지역 대학교 프로그래밍 동아리 연합 icpc-sinchon.io 연합 홈페이지 링크이다. 무엇을 하는 연합인지 그리고 지난 캠프들의 기록들을 확인할 수 있다. 이번 겨울 캠프 구성도 지난여름과 크게 다르지 않았다. - 초급, 중급, 고급 난이도의 수준별 스터디(수업)가 있..

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

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개 세울 것이다. 이때, 모든 센서가 적어도 하나의 집중국의 범위에 있어야..

23295번: 스터디 시간 정하기 1 첫째 줄에는 스터디에 참가하고자하는 참가자 수 N과 스터디 시간 T가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ T ≤ 100,000) 다음 줄부터 참가하고자 하는 참가자들의 시간 정보가 N개 주어진다. 각 정보의 www.acmicpc.net 2021 아주대학교 프로그래밍 경시대회 APC - Div.1 D번 문제이다. 학회 채점 현황에서 다른 분들이 푼 문제들을 보다가 예전에 배웠던 스위핑 기법을 사용하면 될 것 같아서 바로 풀어보았다. N명의 참가자들이 스터디에 참가 가능한 시간이 주어진다. 스터디는 T시간동안 진행될 때, 시간 만족도가 최대인 시간을 찾는 문제이다. 이때, 시간 만족도는 스터디 시간 동안 각 참가자들이 참여할 수 있는 시간들의 합이다. 풀이..

23304번: 아카라카 주어진 문자열 $S$가 아카라카 팰린드롬이라면, AKARAKA를 출력한다. 만약 그렇지 않다면, IPSELENTI를 출력한다. www.acmicpc.net 2021.11.05 기준 실버 2 문제이다. 재귀 함수를 연습해보기에 괜찮은 문제라 생각된다. 문제는 문자열이 하나 주어지고, 그 문자열이 '아카라카 팰린드롬'인지 확인하는 문제이다. 다음 두 조건을 모두 만족해야 '아카라카 팰린드롬'이다. 풀이 재귀함수 rec를 이용하여 문자열이 아카라카 팰린드롬인지 확인하였다. 재귀 함수 rec는 다음과 같다. bool rec(string x) { // 문자열 x가 아카라카 팰린드롬이면 true를 리턴 if (x.size() == 1) return true; string l, r; ll tm..

23061번: 백남이의 여행 준비 1번 배낭이 담을 수 있는 무게는 20이고, 담을 수 있는 최대 가치는 34이므로 효율성은 1.7이다. 2번 배낭이 담을 수 있는 무게는 21이고, 담을 수 있는 최대 가치는 37이므로 효율성은 약 1.76이다. 3 www.acmicpc.net 12번 제출해서 겨우 맞춘 문제이다... 최근에 많이 풀었던 유형의 문제라서 풀이는 바로 알아냈다. 그런데도 12번이나 풀었다. 결론부터 말하면 메모리 초과로 매우매우 고생했다. 혹시 비슷한 고민을 하시는 분이 있을까 봐 풀이의 하단에 메모리 초과를 해결한 방법을 기록해두었다! (실제로 채점 현황을 보면 한 페이지에 한 분 꼴로 메모리 초과가 나는 것을 볼 수 있다...ㄷㄷ) 문제 이해는 어렵지 않다. 물건 N개가 있고 각각 무게..

2021년 10월 17일 새벽 05:00:16 드디어 solved.ac 기준 플래티넘(Platinum V)을 찍었다!! 저번 SUAPC 팀명이 '협곡에서는 플래티넘인 내가 코딩실력은 실버?!' 였는데, 이제는 둘 다 플래티넘이다. 물론, 문제 푸는 실력은 골드도 안되는 것 같지만... (후기는 시험이 끝나고 이어서 작성할 예정입니다... 일단 자랑하고 싶었어요 아 ㅋㅋ) (2021년 10월 30일 추가완료) 글은 그냥 생각나는 대로 쓰는 거라 아무 흐름도 없을 예정이다 ㅎㅎ solved.ac CLASS 솔직히 얘기하면 플래티넘을 찍기 위해 solved.ac에서 날먹아닌날먹을 조금 했다. 골2부터 플래티넘까지는 CLASS를 깨면서 남들보다 점수를 꽤나 쉽게 올렸다. solved.ac에서 CLASS1~5를 ..