PS하는 깃털

문제 링크 : https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 문제 풀이 이 문제에서는 사진틀의 개수와 추천횟수를 주고, 어떤 학생들을 추천했을 때 사진틀에 있는 사진들이 바뀌어 최종적으로 어떻게 되는지 묻고 있다. 나는 이 문제를 풀 때 여러 함수를 정의해서 풀었다. 먼저 사진틀에 사진들이 다 차있는지를 알아보는 full()과, 삭제할 학생을 찾는 remove(), 매 추천마다 사진틀의 시간을 더해주는 addTime()함수를 정의하였..

문제 링크 : https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 문제 풀이 이 문제는 모눈종이의 가로, 세로의 길이와 모눈종이 상의 자르는 선을 주어줬을 때, 나눠진 부분 중 가장 넓이가 큰 부분을 구하는 문제이다. 최대 넓이를 구하려면 단순하게 가장 긴 가로 변과 가장 긴 세로 변의 길이를 구하면 된다. 구하는 방법은 먼저 column, row배열에 자르는 선인지에 대한 정보를 담고 각각의 배열에서 반복문을 1번씩만 돌아 최소길이를 구할 수 있다. ..

문제 링크 : https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제 풀이 이 문제에서는 좌석들의 정보(VIP여부)가 주어졌을 때 가능한 모든 좌석 배치의 경우의 수를 묻는 문제이다. 당연히 VIP 좌석 때문에 나눠진 좌석들끼리는 서로 영향을 주지 못하기 때문에 각각의 경우의 수를 구하고 곱해야겠다는 생각을 했다. 또 이 가능한 경우의 수는 DP를 이용하면 쉽게 구할 수 있었다. n명의 사람이 있고, VIP가 없을 때 가능한 좌석 배치를 D[n]이라고 하면,..

문제 링크 : https://www.acmicpc.net/problem/17615 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 문제 풀이 문제에서는 볼들의 배열이 주어졌을 때 같은 색깔의 볼들을 한 쪽으로 모으는 최소 이동 횟수를 요구하고 있다. 처음 봤을 땐 왼쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우, 오른쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우 모두 나눠서 반복문을 4번 돌아 구한 다음, 최소를 출력하려고 했다. 근데 더 생각해보니 왼쪽이랑..

문제 링크 : https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 이 문제는 기말고사 마지막 시험에서 시간이 남았을 때 심심해서 푼 문제인 만큼, 어렵지 않다. 문제 풀이 문제에서는 레이저로 절단된 쇠막대기의 조각 개수를 묻는 문제이다. 단순하게 기존 쇠막대기 개수에 각 레이저들이 자른 쇠막대기의 개수들을 다 더해주기만 하면 된다. 그 방법으로 "()" 앞에 있는 "("개수에서 ")"개수를 빼주는 식으로 셌다. 또 기존 쇠막대기 개수는 "()"에 포함되는 "..

문제 링크 : https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제 풀이 이 문제는 어떤 배열을 여러번 반전 시행해서 얻어지는 최종 배열을 구하라는 문제이다. 처음 보자마자 남자와 여자가 시행하는 반전시행이 각각 독립적이므로 따로 함수를 만들어 해결해야겠다는 생각이 들었다. 남자의 경우는 배수들만 반전시켜주면 되고, 여자도 대칭적으로 같은지만 확인해주면 되는 것이기 때문에 어렵지 않았다. 시행 착오 마지막에 출력을 할 때 "스위치 상태를 ..

문제 링크 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 미로가 주어진 경우에 최단 경로를 구하는 문제이다. 아주 간단하게 최단경로를 구하는 문제이므로 BFS를 생각해볼 수 있다. 미로 상태를 2차원 배열 map에 bool 형태로 저장해두고(1 : true, 0 : false) (1,1)에서부터 (N,M)까지 true인 경우에만 탐색을 진행하면 된다. 시행착오 한 점으로 이동하는 방법이 여러가지일 수 있는데, 최소로 가는 경로로 업데이트 해주는 작업을 빼먹어서..