문제 출처: https://www.acmicpc.net/problem/25682 25682번: 체스판 다시 칠하기 2 첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 분석 해당 문제는 누적합 관련 알고리즘을 풀면서 발견한 문제입니다. 기존의 체스판 다시 칠하기의 최적화 버전으로, 더 큰 사이즈의 보드와 줄어든 시간 제한의 차이가 있습니다. 기존 체스판 다시 칠하기는 브루트 포스(brute force) 방식으로, 8 x 8 크기의 체스판을 다시 칠하는 최소 개수를 구하는 문제였습니다. 여기에 8로 고정이었던 체스판의 크기를 k로, 시간 제한을 2초 -> 1초로, 보드의 N과 M의 최대..
문제 출처 : https://www.acmicpc.net/problem/2799 2799번: 블라인드 첫째 줄에 M과 N이 공백으로 구분해서 주어진다. (1 ≤ M, N ≤ 100) 다음 줄에는 현재 건너편 아파트의 상태가 주어진다. 모든 창문은 문제 설명에 나온 것 처럼 4*4 그리드로 주어진다. 또, 창문과 www.acmicpc.net 은근 신경써줘야 할 부분이 많은 까다로운 문제였습니다. 저는 이번 문제를 이전 string의 값을 가진 preStr과 새롭게 읽어온 str이라는 두 변수를 활용하였습니다. 벽과 창문으로 이루어진 아파트는 5N+1, 5M+1의 규칙성을 가지기때문에 이를 활용하였습니다. #include #include using namespace std ; int main(){ ios::..
문제 출처 : https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 저는 해당 문제를 다음과 같이 풀었습니다. #include #include using namespace std; int main(){ //(1 ≤ N ≤ 1000, N은 정수) int c, N, temp, sum ; float avg, overRate ; vector students ; vector overRates ; cin >> c ; for(int k = 0 ; k > N ; sum = 0 ; for(int i = 0 ; i..
문제 출처 : https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 저는 이 문제를 loop를 만들어서 ascending인지 descending인지 먼저 파악을 한 후 둘다 아니라면 믹스로 판단하게끔 하였습니다. #include using namespace std; int main(){ ios::sync_with_stdio(); cin.tie(NULL); cout.tie(NULL); // s is Scale ..
