수학2 [백준] 11653 소인수분해 (Java) [11653 소인수분해] 난이도: 실버5 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 나누는 수가 소수인지 판단해주는 방식을 사용하였다. 그런데 계속 시간 초과가 떴다. 왜 그럴까 생각해보니 이미 소수이면 해당 수로 다 나누기 때문에 그의 배수로는 나눌 수 없다. 예를 들면 12 = 2 x 2 x 3 이다. 이 때, 12 % 2 == 0 이므로 12 / 2 = 6 / 2 = 3 을 만들어버린다. 따라서 이후에 4, 6, 8 등으로는 나눌 수 없게 된다. 물론 그 전에 수가 1이 된다면 반복문을 빠져나온다. [JAVA 코드] import java.io.*; public class Main {.. 2022. 5. 26. [백준] 1941 소문난 칠공주 (Java) [1941 소문난 칠공주] 난이도: 골드3 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제 입력 출력 [아이디어] BFS와 백트래킹 그리고 조합을 사용하는 문제이다. 단순한 BFS를 사용하면 십자가모양을 만들어낼 수 없기 때문에 조합을 사용하여 먼저 7명을 선택해준다. 이 때, 5 x 5 로 학생들이 주어지기 때문에 0 ~ 24로 번호를 정하고 조합을 구하면 편하다. n번 학생의 (행, 열)을 구하는 방법은 (n / 5, n % 5) 이므로 번호를 좌표로 변환하는 것은 크게 어렵지 않다. 7명을 모두 선택한.. 2022. 4. 20. 이전 1 다음
