랄뚜기의 코딩일기

https://www.acmicpc.net/problem/24464 24464번: 득수 밥 먹이기 $N$일 치 식단표를 만들 때 가능한 경우의 수를 $1\,000\,000\,007(=10^9+7)$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 프로젝트 하느라 바쁜 득수는 밥 먹을 시간이 부족하다. 그래서 주로 찾는 식당 네 개 중 하나에서 하루에 한 번 밥을 먹는다. 귀찮으면 굶을 때도 있다. 늘 새로운 느낌을 받고 싶었던 득수는 다음과 같은 규칙으로 다음날 갈 식당을 정한다. 첫날에는 굶거나, 임의로 원하는 식당 하나를 골라서 간다. 어제 굶지 않았다면, 오늘은 식당을 가지 않아도 된다. 어제 식당을 가지 않았다면, 오늘은 식당을 가서 밥을 먹어야 한다. 오늘 간 식당은 다음날 가지 않..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 ..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예..

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 문제 Day Of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다. 끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 처음에 bfs를 왼쪽, 위, 오른쪽, 아래 방향으로 우선 순위를 줘서 탐색하면 해결 될 줄 알았다. 하지만 이렇게 bfs를 구현할 경우 탐색 순서는 다음과 같다. 따라서 나는 우선순위 큐 stl을 이용하여 거리 > y값이 작은 좌표 > x값이 작은 좌표 순를 우선순위로 정렬한 다음 bfs를 이용하여 문제를 풀었다. 조심해야 할 점은 pop을 할 때 조건을 만족하는지 검사해야 한다는 것이다...

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 전형적인 이분탐색문제이다. 주의해야 할 점은 upperbound는 구하고자 하는 값보다 큰 값이 처음으로 나오는 인덱스를 출력하므로 반복문을 돌 때 H를 포함시켜야 한다는 것이다. #include #include #include #include #include #include #include #include #include #include #define endl '\n' #define ll long ..

https://www.acmicpc.net/problem/11660 이 문제를 풀기 위해서는 dp[i][j]가 1,1부터 i,j까지 영역의 합을 나타내야 한다. 위와 같은 값이 주어졌다고 가정해보자. 배열의 각 칸에는 1,1부터 i,j까지의 영역의 합을 입력해야 한다. ?에는 1+2+5+7, 즉 15가 와야 한다. 파란 영역(1+5)과 빨간 영역(1+2)을 활용하여 ? 값을 구하기 위해서는 중복되는 부분(1)을 빼줘야 한다. 점화식을 세우면 dp[i][j]=input[i][j]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1] 이란 것을 직관적으로 알 수 있다. 이제 dp 배열을 활용하여 답을 구하면 된다. 초록색 영역의 합을 구해야 된다고 가정하자. 초록색 영역=빨강색 영역-주황색 영역-노..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 그냥 LCS문제인줄 알았는데 공통되는 문자열을 구해야하기 때문에 공통된 문자들이 연속적이어야 한다는게 기존 LCS문제와 달랐다. 기존 LCS에서 LCS[i][j]가 나타내는 것이 한 문자열의 i번째와 다른 문자열의 j번째까지 공통된 문자의 개수였다면 이 문제에서 LCS[i][j]가 의미하는 바는 한 문자열의 i번째와 다른 문자열의 j번째까지의 공통 부분 문자열의 크기를 저장해야 한다. ..