정리와기록 블로그

문제: www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 접근: 회의실을 끝나는 순서대로 정렬합니다. (이때 같은 시간에 끝난다면 시작 시간이 빠른 순서대로 정렬합니다) 정렬한 배열을 순회하면서 '이전 회의 시간이 끝나는 시간' > N; for (int i = 0; i > temp.first >> temp.second; rooms.push_back(temp); } sort(rooms.begin(), rooms.end(), comp); int cnt = 0; long last = -1; for (int i = 0; i < N; i..

문제: https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 접근: 카운터 배열을 마련하여, 방 번호가 몇 번까지 나왔는지 체크합니다. 새로운 셋이 마련되어야 하는 순간은 방 번호가 현재 갖고 있는 셋보다 더 많이 주어졌을 때(numOfCounter < counter[num]) 인 경우입니다. 이런 경우에는, 셋을 하나 더 받아야 해당 번호를 수용할 수 있다는 뜻이기 때문입니다. 6이나 9일 경우에는 9나 6의 번호를 보고 판별합니다. 코드: namespace forAlgo2 { class Program { static string str..

문제: https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마�� www.acmicpc.net 접근: 스택을 이용해서 풀면 됩니다. 비어있을 때 닫는 괄호가 나오면 바로 종료하는 등 예외 처리를 해줍니다. 코드: #include #include #include #include using namespace std; string Line; string CheckBalance(stack, string); int main() { while (1) { stack Stack;..

문제: https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 접근: c / d / l / j / n / s 여섯가지 알파벳의 경우에만 크로아티아 특유의 알파벳인지 확인하면 됩니다. 만약 해당 알파벳이면서, =, - 등의 기호가 따라오는 경우 크로아티아 특유의 알파벳으로 확인하고 순회하는 인덱스도 +1 또는 +2만큼 넘어갑니다. (코드 참고) 코드: #include #include using namespace st..

문제: https://www.acmicpc.net/problem/2804 > A >> B; int row = -1, col = -1; for (int i = 0; i < A.length(); i++) { for (int j = 0; j < B.length(); j++) { if (A[i] == B[j]) { col = i, row = j; break; } } if (row != -1) break; } for (int i = 0; i < A.size(); i++) mat[row][i] = A[i]; for (int j = 0; j < B.size(); j++) mat[j][col] = B[j]; for (int i = 0; i < B.size(); i++) { for (int j = 0; j < A.siz..

문제: https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1≤x≤12)와 y(1≤y≤31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net 접근: 행을 1,2,3, ..., 12로 하고 열을 1,2,3, ..., 31로하는 달력 배열(year[month][day])을 선언한다. 그리고 달력 배열의 값에는 요일을 넣는데, 0부터 6까지 각각 월요일부터 일요일이라고 정한다. 2일부터 각 월의 마지막일까지(예: 3월의 끝은 31일) (전날 + 1) % 7을 해준다. 1일은 (전 월의 마지막일 + 1 % 7..

문제: https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다. www.acmicpc.net 접근: 비교 규칙에 따라 다음과 같이 비교 함수를 구현한다. // 각가 번호, 금,은,동, 순위 typedef struct { int no, g, s, b, rank; } order; bool op(order a, order..

문제: https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 접근: 모든 경우의 수를 이용하려면, 부분합 배열을 사용해도 O(N^2)이 발생하기 때문에 시간 초과가 발생한다. 처음에 나는 부분합 배열을 받고, A[i] - A[j-1] == M 이되는 경우의 수를 탐색하되, 1 j -1에 해당 조건에 맞는가? 가 핵심 for (int i = picked.back(); i >= 1 && (A[picked.back()] - A[i]