반응형
[BOJ1339] 단어 수학 (Java, 그리디, 완전 탐색)
알고리즘/탐욕(그리디)2025. 1. 20. 20:59[BOJ1339] 단어 수학 (Java, 그리디, 완전 탐색)

문제 링크https://www.acmicpc.net/problem/1339  풀이- 완전 탐색 + 비트마스킹, 그리디 풀이- 각 알파벳을 0 ~ 9 숫자로 중복 없이 치환하여서 최대값을 구하는 문제 (같은 알파벳은 같은 숫자로 바껴야 하고, 중복 숫자x) 처음 완전 탐색 + 비트 마스킹으로 풀이했다. 그런데 공간복잡도와 시간복잡도가 너무 높이 나왔다.그래서 그리디 풀이 방법을 고민했는데, 아이디어가 전혀 떠오르지 않아 블로그를 참고하여 풀이했다 1) 완전 탐색 + 비트 마스킹- 중복을 제외한 알파벳을 구한다 - 알파벳별로 9~0 사이의 숫자를 할당하면서 완전 탐색을 수행한다- 이때 숫자 사용여부를 비트 마스킹 기법을 사용하였다 ( 9 ~ 0 자리의 비트를 표현하면 되므로 int 로 충분)- idx 가 알..

반응형
image