반응형
1120
-
BOJ) 문자열알고리즘/백준 2020. 7. 21. 15:29
문자열 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 풀이 문자열 두개가 주어질 때, 오른쪽 문자열의 길이는 항상 왼쪽보다 크다. 왼쪽 문자열의 맨 앞이나 맨 뒤에 a~z 문자 하나를 적절하게 배치했을 때, 왼쪽과 오른쪽의 문자열의 인덱스가 다른 수의 최소값을 찾는 문제다. 문제의 조건에 최대 길이가 50이라고 주어졌지만, 이를 먼저 확인하지 않고 brute force라 dfs로 그냥 모든 경우의 수를 조합했다. 하지만, 메모리 초과가 떠서 위의 조건을 추가적으로 ..