www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 처음에 문제를 잘못 읽어서 아래 코드에서 apps가 메모리, Mem이라는 녀석이 비용에 해당합니다. (c1,c2,....) 이 문제의 핵심은 가능한 메모리 별로 dp를 구하는 것입니다. 처음에 문제 접근을 잘못해서 구현이 되지 않아 구글링으로 힌트를 조금 얻었습니다. dp[i]를 비용이 i일 때 가능한 메모리의 최댓값으로 처리합니다. 여기서 최댓값으로 처리하는 이유는, 최종적으로 계산할 때, 앞에서 부터 dp를 앞에서..
www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 기말고사 기간으로 인해 2주만에 글을 씁니다. 다음주부터는 본가에 내려가서 블로그에 안 올렸던 django 프로젝트와 암호경진대회 5번 문제풀이, CS와 수학의 이론 내용을 블로그에 정리할 예정입니다. 삼성 SW 기출문제인 감시 문제입니다. 한 방향, 양방향, 직각방향, 세 방향, 네 방향을 바라보는 cctv가 주어졌을 때 사각지대의 최소값을 구하면 됩니다. 각 cctv가 1,2,3,4,5번으로 주어..
www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 날은 춥지만 요즘 같은 코로나 시대에 밖에서 맥주를 먹고 싶어 골라본 문제입니다. 여담으로 본가에는 12/2 10시 기준으로 경남 전체에 7명이 나왔네요. 물론 지금 전세계 어디든 안 위험한 곳이 없지만 서울이 193명인것에 비해 아주 적은 수치라 부럽기도 합니다. 좁은 고시원 같은 방에서 몇 달을 보내는 건지.... 조금 더 여담을 말하면 여름에 본가에 내려갔더니 저를 경계하여 너무 슬펐습니다. 집이랑 ..
www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 지난 주에 교내 알고리즘 대회에서 탈탈 털려서 (구현은 대체적으로 해냈지만 테스트 케이스를 통과 못해서 상은 받지 못했다....) 기본 문제를 하나 풀어보았습니다. 간단한 그래프 문제입니다. 방향 그래프에서 모든 정점에서 모든 정점으로 가는 경로의 유무 (최단 경로X) 만 판단하면 되는 간단한 문제입니다. 최단 경로가 아닌 경로의 유무만 알면되기에 다양한 방법이 있지만, 플로이드 와샬 알고리즘을 이용하여 풀었습니다. 플로이드 와샬 알고리즘이란 가중그래프..
www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 5000자리 이하의 암호문이 주여졌을 때, 가능한 경우가 얼마인지 구하는 문제이다. (modulo 1000,000) 문제에서 A:1 ~Z:26으로 대응되게하였으므로 앞자리가 0이면 암호가 성립되지 않는다. 또한, 70 과 같은 경우는 앞자리가 0이 아니지만, 7 다음으로 0인 케이스가 존재하기 때문에 이러한 경우도 안 된다. 되는 경우는 다음과 같다. 해당 자리수에 가능한 수를 dp배열을 이용해 표기하면 점화식은 다음과 같다. ..