[종만북] STRJOIN - 문자열 합치기 (자바 java)
알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-STRJOIN 풀이 N개의 문자열이 주어질 때, 여기서 2개를 선택해 새로운 문자열을 만들고, 그 길이의 합이 비용이 된다. 이걸 하나의 문자열만 남을 때 까지 반복하는 문제이다. 합치는 순서가 중요할텐데, 4개의 문자열이 있고 각 길이가 A, B, C, D라고 해보자. (A)와 (B)를 합치면 (A+B)의 문자열이 된다. 그럼 문자열은 현재 (A+B), (C), (D)가 있다. (A+B)와 (C)를 합치면 (A+B+C)가 된다. 그리고 다시 (D)와 합치면 (A+B+C+D)가 된다. 여기서 비용에 들어간 횟수를 살펴보면 'A'와 'B'는 비용에 총 3번, 'C'는 2번, 'D'는 1번 더해졌다. 따라서 직관적으로 여러번 합쳐질 녀석..
2023. 4. 14.
[종만북] PICNIC - 소풍 (자바 java)
알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-PICNIC 풀이 n명을 일렬로 놓는 경우의 수는 n! 이다. 따라서 일렬로 놓고 2명씩 쌍을 짓는다고 생각해보면 O(C x n!)가 필요하므로 통과할 수 없다. 더 효율적으로 하려면 2명씩 짝지어볼 수 있다. 이 때, 주의할 점은 아래의 경우들은 모두 같은 경우라는 점이다. '일부만 다르더라도 다른 방법' 이라고 써져 있는 부분은 짝이 다를 경우이지, 이미 정해진 쌍에 대해서는 상관이 없다. (0, 1), (2, 3) (0, 1), (3, 2) (1, 0), (2, 3) (2, 3), (0, 1) (3, 2), (1, 0) ... 등 그리고 모든 학생이 쌍에 포함되어야 하므로, 그냥 쌍을 지어주는 방향을 고정시켜도 결과는 동일하다...
2023. 3. 20.