수학

문제 링크 1. 처음 보고 정확한 식은 기억이 안 났지만, 고등학교 확통 시간에 배운 내용이 대략적으로 떠올랐다. 이 문제는 수학과 DP를 섞어 푸는 문제이다. 2. 기억이 안났던 식은 다음 식이였다. $_{n}C_{r}=_{n-1}C_{r-1}+_{n-1}C_{r}$ 이 공식은 파스칼의 삼각형에서도 구할 수 있다. 관련 내용은 아래 참고 블로그에서 공부하자. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[][]..

문제 링크 1. sloved에 그리디 문제로 분류되어 있길래 탐욕스러운 사고기법을 적용해보려 했지만 떠올리지 못했다. 해설을 찾아보니 그리디 문제로 풀면 못푼단다. 이 문제의 분류를 수학, 백트래킹으로 바꿔야 할 듯하다. 중학교 때 이런 문제와 비슷한 창의 수학 문제를 풀었던 것 같은데.. 흠 2. 수학적 방식은 매우 심플하면서도 획기적이다. 높은 자릿수의 알파벳에 가중치를 부여하는 방식이다. $GCF$ 와 $ACDEB$ 두 가지 단어를 예로 들면, $GCF = 100G+10C+F$ $ACDEB = 10000A+1000C+100D+10E+B$ 이므로 $GCF+ACDEB = 10000A+1010C+100D+100G+10E+B+F$ 이다. 따라서 높은 자릿수인 $A$부터 $9$를 넣으면 단어의 합이 최댓값이..