16197번 - 두 동전(bfs)
문제: 풀이:최소 몇번 움직여야하는지 맞춰야 하는 문제이다.이를 dfs로 풀게되면 모든 경우의 수를 다 살펴봐야하지만, bfs로 풀면 가장 처음 목적지에 도착할때, 그 횟수를 반환해 줄 수 있다. 동전이 움직일때 꼭 고려해야 하는 사항은 두개이다.동전의 움직임을 기록하고, 중복된 위치에 동전이 있지 않게 해준다.두 동전의 지금 위치를 기록한다.1 2 두 동전의 위치를 바꿔서 기록한다.2 1 두 동전이 각 동전의 자리에 한번에 모여있는 상황을 기록한다.1, 2 두 동전이 동시에 판 밖으로 떨어지면 안된다.또한 동전은 4방향으로 움직일 수 있으니, 4방향 탐색법을 이용하면 된다. 아래 static 메서드를 이용하도록 하자.static int[][] move = {{1,0}, {-1, 0}, {0, 1}..
2024. 9. 26.
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.
