brute-force
-
[Algo Rhythm🕺💃]BOJ 2309 - 일곱 난쟁이Algo Rhythm🕺💃/BOJ 2021. 6. 22. 20:02
문제 분석 문제에서 주어지는 아홉 난쟁이들의 키의 합은 일곱 난쟁이들의 키의 합인 100보다 크다. 따라서 이 문제는 $i$번째 난쟁이와 $j$번째 난쟁이 $(1 \le i, j \le n)$의 합이 초과값과 일치하는 $(i, j)$쌍을 찾는 문제로 이해할 수 있다. 문제 풀이 아홉 난쟁이의 키를 배열에 저장한 뒤, 이를 오름차순으로 정렬한다. 왜냐하면 일곱 난쟁이의 키를 출력할 때 오름차순으로 출력해야 하기 때문이다. 다음으로 이중 반복문을 통해 $(i, j)$쌍을 찾는다. 만약 찾았다면 $i$번째 난쟁이와 $j$번째 난쟁이를 제외한 모든 난쟁이들의 키를 차례대로 출력한 뒤 프로그램을 종료한다. 복잡도 분석 난쟁이 $n$명의 키가 입력으로 주어질 때, 시간 복잡도와 공간 복잡도는 다음과 같다. 시간 복..
-
[Algo Rhythm🕺💃]BOJ 20170 - Commemorative DiceAlgo Rhythm🕺💃/BOJ 2021. 6. 21. 03:26
문제 분석 주사위 게임을 하는 첫번째, 두번째 플레이어를 각각 A, B라고 하고 A와 B의 주사위 중 임의의 한 면에 적힌 숫자를 각각 $\alpha, \beta$라고 하자. 이때 주사위는 6면이기 때문에 A와 B가 주사위를 던져서 나올 수 있는 경우의 수는 $6 \times 6 = 36$이다. 그리고 A가 B를 이기는 경우의 수인 $N_{win}$은 $\alpha \gt \beta$를 만족하는 모든 $\alpha$의 수와 같다. 따라서, A가 B를 이길 확률은 $N_{win} \over 36$이다. 이때, 문제에서 요구하는 것은 '더이상 나눌 수 없는' 분수 형태로 출력하는 것이기 때문에 분자와 분모를 최대 공약수로 나눠서 출력해야 한다. 문제 풀이 A와 B의 주사위 정보를 각각 배열에 저장한 뒤, $..