본문 바로가기

Problem Solving1486

[백준] 16943 숫자 재배치 - Backtracking / Java • 문제 링크 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net • 풀이 과정 입력받은 문자열 a를 순열으로써 charAt() 으로 인덱스를 탐색하고, boolean 배열을 활용한 백트래킹으로 구한다. 이때 문제에 주어진 조건 상 구해진 순열이 0 으로 시작하면 안되고 b 보다 작거나 같아야 하므로 순열의 하나의 경우의 수를 c 이고 탐색을 수행할 반복문의 인덱스를 i 라고 할 때, 현재 문자열 a 에서 탐색한 숫자가 0 이거나 (a.charAt(i) - '0' == 0), 구해진 순열이 .. 2022. 8. 1.
[백준] 16922 로마 숫자 만들기 - Backtracking / Java • 문제 링크 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net • 풀이 과정 4개의 수 중에서 n개의 순열을 찾되, 서로 다른 수를 찾아야 하는 문제의 조건을 고려하여야 한다. 예를 들어 n = 6 일 때, I I I I I L = 1 + 1+ 1+ 1+ 1 + 50 = 55, V X X X X X = 5 + 10 + 10 + 10 + 10 + 10 = 55 과 같이 합이 중복인 값이 존재한다. 따라서 1 ≤ N ≤ 20 조건에 의해 합의 최대 값은 50 * 20 = 1000, 인덱스의 범위를 벗어나지 않기 위해 크기가 1001 인 boolean 배열을 생성하여 중복을 검사한다. 백트래킹을 활용하여 순열의 .. 2022. 7. 31.
[백준] 1744 수 묶기 - Greedy / Java • 문제 링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net • 풀이 과정 수열의 합의 최대 값을 만들기 위해선 양수와 음수가 곱해져서 더 큰 음수를 만들지 않고, 음수와 음수끼리 곱하여 양수로 만들거나 0 와 음수를 곱하여 음수를 제거하여야 한다. 양수의 경우 내림차순으로 정렬하여 큰 순서대로 두 수를 곱하거나, 연산을 하는 두 수 중 1이 존재 할 시 두 수를 곱하는 대신 더한다. 따라서 양수는 양수끼리 연산하고, 음수는 0을 포함한 음수끼리 연산하여야 하므로 서로 다른 List 객체 pn (posit.. 2022. 7. 30.
[백준] 12904 A와 B - Greedy / Java • 문제 링크 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net • 풀이 과정 A 에서 B 로 변환하는 과정에서 재귀 호출 함수로 풀이 시 두 가지 연산의 모든 경우의 수를 모두 고려하므로 시간 초과가 발생한다. 따라서 B 에서 A 로 변환하여 B 의 끝자리의 문자에 따라 한 가지 경우의 수만 고려하는 방식으로 접근한다. A 문자열을 s, B 문자열을 StringBuilder 객체 t 에 입력받고 연산에 의해 두 문자열의 길이가 같을 때까지 while 문을 수행한다. t 문자.. 2022. 7. 29.
[백준] 1285 동전 뒤집기 - Greedy / Java • 문제 링크 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net • 풀이 과정 문제에 제시된 조건에 의하면 각 동전의 값은 대응되는 행 또는 열을 변환할 때 그 값이 결정된다. 해당 풀이에서는 n = 3, n * n 의 행렬에서의 행의 변환의 모든 경우의 수를 구하며 이를 1 ~ (1 2022. 7. 28.
[백준] 2138 전구와 스위치 - Greedy / Java • 문제 링크 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net • 풀이 과정 n 개의 전구의 모든 값을 앞에서 부터 XOR 연산을 수행하여 모든 경우를 확인한다. 이때 1 ~ n 의 범위 내 i 번째 연산에 의해 i - 1 의 값이 최종적으로 결정되므로 두 배열의 i - 1 번째 값을 비교하며 0번째 연산의 수행 여부에 따라 1번째 연산의 수행 여부가 결정되므로 두 경우를 모두 수행한다. 재귀 함수의 깊이를 idx 변수, 연산의 횟수를 cnt 변수로 지정하고 input[idx - .. 2022. 7. 27.

티스토리툴바