728x90 백트래킹6 [JAVA]백준 15654번: N과 M(5) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 설명 N개의 자연수 와 자연수 M이 주어졌을 때 N개의 자연 수 들 중에서 M개를 고른 수열을 모두 구하는 프로그램을 작성하시오. 수열은 사전 순으로 증가하는 순서로 출력해야 하며 중복되는 수열이 없어야 한다. 2. 풀이 시간복잡도 : O(N!) 수열은 사전 순으로 증가하는 순서로 출력해야 하기에 먼저 N개의 자연수를 정렬해준다. 그 다음, 0번째부터 N번까지 돌아가며, 전에 .. 2021. 8. 18. [JAVA]백준 21772번: 가희와 고구마 먹방 https://www.acmicpc.net/problem/21772 21772번: 가희의 고구마 먹방 첫 번째 줄에 맵의 세로 크기 R, 가로 크기 C, 가희가 이동하는 시간 T가 주어집니다. 두 번째 줄부터 R+1번째 줄까지 길이가 C인 문자열이 주어집니다. 주어지는 문자열에 있는 문자는 가희를 www.acmicpc.net 1. 문제 설명 오빠는 방 안에 고구마를 숨겨두었다...! 가희는 1초마다 상하좌우 방향 중 한 방향으로 1번 이동하거나, 이동하지 않고 그 자리에 머물 수 있다. 가희가 이동한 지점에 고구마가 있으면 고구마를 먹는다. 고구마를 먹는데 걸리는 시간은 없다. 가희가 고구마를 먹으면 고구마는 그 자리에 다시 생기지 않는다. 가희가 현재 위치에서 T초만큼 이동했을 때 최대 몇개의 고구마를.. 2021. 8. 18. [JAVA]백준 2580번: 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 1. 문제 설명 스도쿠가 주어졌을 때 빈칸 (0)을 채우는 문제. 스도쿠 판을 채우는 방법이 여럿인 경우 그중 하나만 출력 2. 풀이 백트래킹 + 비트 연산으로 풀었다. 스도쿠 규칙 상 1 ~ 9까지의 숫자가 겹치지 않게 가로줄, 세로줄, 3*3 정사각형 안에 하나씩 존재해야 한다. 입력 값이 0인 경우에는 list에 저장하였고, 0이 아닌 경우에는 row, column, box (3*3 정사각형.. 2021. 7. 20. [JAVA]백준 1759번: 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. 문제 설명 글자 수와 암호의 길이가 주어진다. 주어진 글자를 이용하여 암호를 만드는데, 암호는 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열 되었을 것이라고 추측한다. 암호는 최소 한개의 모음과 최소 두개의 자음으로 구성되어야 한다. 2. 풀이 백트래킹으로 풀 수 있는 문제이다. 암호는 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되기 때문에 암호의 X번째 알파벳은 이전 암호의 알파.. 2021. 7. 20. 이전 1 2 다음 728x90
