일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- 비동기
- GitHub
- 17822
- npm
- commited
- 백준
- 카카오코드페스티벌
- JavaScript
- 1868
- graph
- web
- HTTP
- Ajax
- 소형기관차
- 타겟넘버
- 알고리즘
- SOCKET
- boj
- JSP
- 파핑파핑지뢰찾기
- react
- Git
- staged
- SWEA
- 달팽이는올라가고싶다
- Java
- node.js
- 응답코드
- 17471
- 2869
- Today
- Total
devlog
[BOJ] 백준 15954 인형들(카카오코드페스티벌)-java 본문
문제
카카오프렌즈 스토어를 관리하는 브라이언은 어떠한 특정한 곳에 인형들을 배치하고자 하는데, 그곳에 인형들을 선택하는 방법은 다음과 같다:
- 먼저 비슷한 인형이 가깝게 위치하도록 서로 다른 N개의 인형을 종류당 한 개씩 일렬로 배치한다.
- 그 후, 선호하는 사람의 수의 표준편차가 최소가 되는, K개 이상의 연속된 위치에 있는 인형들을 선택하여 그들을 같은 곳에 배치한다.
위의 방법으로 인형들을 선택했을 때, 선택된 인형들의 선호하는 사람의 수의 표준편차를 구하여라.
N개의 수 a1, a2, …, aN이 주어져 있을 때, 통계학에서 (산술) 평균은 (a1 + a2 + … + aN) / N 으로 정의한다. 이를 m으로 정의하자.
또한, 분산은 ((a1 - m)2 + (a2 - m)2 + … + (aN - m)2) / N으로 정의하고, 표준 편차는 분산의 음이 아닌 제곱근으로 정의한다.
첫 번째 줄에 N과 K가 주어진다. N은 1 이상 500 이하의 정수이고, K는 1 이상 N 이하의 정수이다.
두 번째 줄에는 N개의 정수가 입력되며, 이는 인형이 일렬로 나열된 순서대로 인형을 선호하는 사람의 수이다.
각 수는 모두 106 이하의 음이 아닌 정수이다.
선택된 인형들을 선호하는 사람의 수의 표준 편차를 출력한다. 출력한 결과와 실제 답을 비교하였을 때의 상대/절대 오차가 10-6 이하
인 경우에만 정답으로 인정한다.
문제:https://www.acmicpc.net/problem/15954
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | import java.io.*; import java.util.*; public class doll { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[] arr = new int[n]; // 인형을 선호하는 사람의 수를 저장할 배열 double variance = 0, tmp = 0, average = 0, stdDeviation = 0; // 분산,평균,표준편차 double min = 10000000; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); } for (int i = 0; i <= n - k; i++) { int count = k; // k개 이상이기때문에 k개부터 하나씩 늘려가면서 표준편차가 최소일 때를 찾아야 함 while (i + count <= n) { // 배열의 끝까지 연속할 경우를 확인해야하므로 i+count가 n보다 작거나 같을때까지만 반복 tmp = average = variance = stdDeviation = 0; // for (int j = 0; j < count; j++) { tmp += arr[i + j]; } average = tmp / count; // 평균 구하기 tmp = 0; for (int j = 0; j < count; j++) { // 분산구하기 tmp += (arr[i + j] - average) * (arr[i + j] - average); } variance = tmp / count; // 분산 구하기 stdDeviation = Math.sqrt(variance); // 표준 편차 구하는 함수 min = Math.min(min, stdDeviation); count++; } } System.out.println(String.format("%.12f", min)); 0 } } | cs |
풀이
이 문제는 n과 k가 주어졌을 때 n개의 인형에 대학 각각의 선호도를 데이터로 입력받고 그 선호도에 대해서 적어도 k개 이상 연속하는 데이터중에 표준편차가 최소일 때를 찾아야 하는 문제입니다. k개로 고정이 되었다면 처음부터 한개씩 뒤로 이동하면서 연속하는 부분집합을 구해서 비교하면 간단했겠지만 k개 이상이므로 첫번째 데이터부터 연속할 때 k개,k+1개,k+2개,..,n개 이런식으로 항상 확인 한 후 두번째 데이터 부터 k개,k+1개... 이렇게 확인하는 문제입니다.
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 백준 2583 영역구하기-java (0) | 2019.03.18 |
---|---|
[BOJ] 백준 11403 경로찾기-java (1) | 2019.03.12 |
[BOJ] 백준 10250 ACM호텔-java (395) | 2018.12.05 |
[BOJ] 백준 1193 분수찾기-java (350) | 2018.12.04 |
[BOJ] 백준 2292 벌집-java (415) | 2018.12.04 |