2023번 - 신기한 소수(bfs, 백트래킹)
문제:7331은 소수인데, 733도 소수 73도 소수 7도 소수이다.이런 숫자를 신기한 소수라고 하자.숫자 N이 주어졌을 때, N자리 수 모든 신기한 소수들을 출력해라. 풀이:예시 7331에서 고려해야 할 숫자는 7 73 733 7331 모두 4개이다.만약 왼쪽부터 첫 자리 수가 소수가 아니라면 그 이후 수는 고려할 필요가 없다.즉, 왼쪽자리 숫자부터 고려하면 된다는 뜻이다.신기한 소수를 만들려면 아래와 같은 규칙이 동반되어야 할 것이다.왼쪽부터 첫째 자리 수가 소수이려면, {2, 3, 5, 7} 중 하나여야 한다.둘째 자리 이상의 수가 소수이려면, {1, 3, 7, 9} 중 하나가 마지막수로 붙어야 한다.어떤 수든 두자리 수 이상의 수가 소수이려면 {0, 2, 4, 5, 6, 8}은 마지막 숫자로 ..
2024. 9. 20.
12969번 - ABC(bfs, dp)
문제: 풀이:문자열 ABC의 유효한 쌍은 'AB', 'AC', 'BC'이다.A만 입력시에는 유효한 쌍이 없고,AB까지 입력시에는 유효한 쌍이 ABABC까지 입력시에는 유효한 쌍에 AC, BC가 추가된다.위 예시를 통해 알 수 있는 것은 아래와 같다.A 입력시 고려할 것은 없다B 입력시 앞에 있는 A의 수만 고려하면 된다.C 입력시 앞에 있는 A, B의 수를 고려해야 한다.C를 문자열의 앞 부분에 추가할 때 고려해야 할 것은 없다.즉, A의 수, B의 수, C의 수, 유효한 쌍의 수 4개를 기록해 놓으면, 다음 문자를 추가할 때 계산을 편하게 할 수 있다.계산 과정은 아래와 같다.기록한 정보를 꺼내온다.유효한 쌍의 수가 K와 같다면, "C * (N - (A + B + C의 수) ) + 만들어진 문자"를 출..
2024. 9. 13.
10942번 - 팰린드롬?(dp, br, st)
문제: 풀이:먼저, 팰린드롬이 뭔지 알아야한다.(1, 2, 1), (a, b, c, b, a), (가, 나, 다, 나, 가) 등 대칭되는 문자들의 모음을 팰린드롬이라고 한다.문제에서 알려주지않아 햇갈릴 수도 있지만, (1, 1), (1, 2, 2, 1)도 팰린드롬이며, 문자의 수가 짝수든 홀수든 상관 없다. 자 그럼 문제에서 준 보기를 이용해 문제를 풀어보자.1213121이렇게 배열이 주어졌다.먼저 보기에서 설명하듯 숫자가 1개 있을 때는 모두 팰린드롬이다. 1(1)2(2)3(1)4(3)5(1)6(2)7(1)길이: 111221133112211팰린드롬?ppppppp숫자가 두개 있을 때는 앞 뒤만 비교하고 같은 수라면 팰린드롬이다. 1(1)2(2)3(1)4(3)5(1)6(2)7(1)길이: 1112211331..
2024. 9. 12.
