문제 10211번: Maximum Subarray크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 문제이다.www.acmicpc.net 풀이 연속된 부분 수열의 합 중 최댓값을 구하는 전형적인 DP(Dynamic Programming) 문제이다. 입력받은 현재 값을 더해가며 최대 부분합을 갱신한다. 이때, 합이 음수라면 새로운 구간을 시작하면 된다. 코드 fun main() { val sb = StringBuilder() repeat(readln().toInt()) { val num = readln().toInt() val arr = readln().split(' ').map { it.toI..

문제 2303번: 숫자 게임N명이 모여 숫자 게임을 한다. 각 사람에게 1부터 10 사이 숫자가 적힌 다섯 장의 카드가 주어지고, 이 중 세 장을 골라 합의 일의 자리 수가 가장 큰 사람이 이긴다. 같은 값일 경우 번호가 큰 사람이 승리한다.www.acmicpc.net 풀이 5개의 숫자 중 3개를 선택해 (a + b + c) % 10 값이 가장 큰 사람을 찾는 문제이다. 모든 가능한 조합을 확인하면서 최대값을 갱신하면 해결할 수 있다. 코드 fun main() { var ans = 0 var max = 0 repeat(readln().toInt()) { idx -> val num = readln().split(' ').map { it.toInt() } var..

문제 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데N종류의 아이스크림 중 3가지를 고르려 한다. 그러나 M개의 섞어 먹으면 안 되는 아이스크림 쌍이 주어질 때, 이들 조합을 피하면서 선택할 수 있는 경우의 수를 구하는 문제.www.acmicpc.net 풀이이 문제는 친구 관계를 기반으로 세 명으로 이루어진 팀(삼총사) 수를 세는 문제이다. 각 팀은 세 명 모두 서로 친구가 아닌 경우에만 만들 수 있다. pair[a][b] = true로 친구 관계를 저장합니다. 친구 관계는 양방향이므로 pair[b][a] = true도 함께 설정한다. 3중 for문으로 모든 삼총사 후보 탐색한다.for(i in 1..n) for(j in i+1..n) for(k in j+1..n)i 코..

문제 21921번: 블로그N일간 블로그 방문자 수가 주어질 때, 연속한 X일 동안 방문자 수 합이 가장 큰 값을 구하고 그 기간이 몇 개 있는지 출력하는 문제.www.acmicpc.net 풀이 이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 이용해 연속된 일 동안의 방문자 수 합의 최대값과, 그 최대값이 나타나는 횟수를 구할 수 있다. 첫 번째 구간(0 ~ num-1일)의 방문자 합을 구해 sum과 max로 초기화한다. 이후 하루씩 구간을 옮기며, 이전 구간의 첫 번째 값을 빼고 새로운 날짜의 방문자 수를 더해 새로운 합을 구한다. sum > max인 경우 → 새로운 최대값 발견, max 갱신 후 cnt = 1 sum == max인 경우 → 동일한 최대값 구간 추가, cnt++ 모든..

문제 1268번: 임시 반장 정하기1학년부터 5학년까지 지내오면서 한 번이라도 같은 반이었던 학생이 가장 많은 학생을 임시 반장으로 정하려 한다. 각 학생들이 각 학년마다 속했던 반 정보가 주어질 때, 그 학생 번호를 출력하는 문제이다.www.acmicpc.net 풀이 입력받은 배열 student[i][j]는 i번 학생의 j학년 때 반 번호를 의미한다. 총 5학년 동안의 반 정보를 2차원 배열에 저장한다. check[j][k]를 true로 설정해, j번 학생과 k번 학생이 한 번이라도 같은 반이었던 경우를 표시한다. 각 학생마다 check[i] 배열을 확인해 true의 개수를 세면, 해당 학생이 몇 명과 같은 반이었는지 알 수 있다. 가장 많은 학생과 같은 반이었던 사람의 번호(i+1)를 출력한..