백준(boj)
[JAVA]2758 로또(dfs 시간초과/ dp)
📚 문제 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 🔍 아이디어 처음 문제를 봤을 때는 그냥 dfs를 이용하는 풀이를 생각했다 -> 그래서 3번 시간 초과 났다 (dfs에서도 최적화 가능한 줄 알고 여러 번 도전했다.) 3번이나 시간초과 후에는 dp를 떠올렸다. 생각해보니까 가능하다는 생각이 들었다. 그래서 dp로 수정하고 제출하니까 16%에서 틀렸습니다 라는 메시지가 나와서 당황했다. 뭐지.. 설마 타입문제인가 라는 생각으로 엣지 케이스를 넣으니까 음수로 나와서 오버플로우발생을 확인했다 이후에 long으로 선언..
