백준 19535 - ㄷㄷㄷㅈ

백준 19535 - ㄷㄷㄷㅈ

https://www.acmicpc.net/problem/19535

★풀이

처음엔 시간복잡도를 고려하지 않고 말 그대로 모든 노드를 일일이 다 계산해주었다. 하지만 총 노드의 개수가 최대 30만개인데 그것을 일일이 따져나가면서 계산한다면(나 같은 경우에는 인접리스트를 만들고 DFS를 통해 탐색했다.) 아무리 백트래킹으로 최적화를 시킨다 한들.. 노드를 고려할 때마다 거기에 연결된 또 다른 노드들을 최악의 경우 약 30만번을 더 고려해야하기 때문에 딱 봐도 답이 없게 된다. 시간을 고려하지 않고 문제를 풀면 나 처럼 시간을 낭비하게 된다.

시간복잡도를 고려하고 다시 코드를 짤 때는 수학적 지식을 통해 nC3이므로

ㅈ -> 한 노드에서 연결된 n개의 다른 노드들 중에 3가지를 고른다 : n*n-1*n-2/(3*2*1)

ㄷ -> 한 노드(A)와 그 노드와 연결된 다른 노드(B)를 하나 더 선택하여(총 2개)

A에서는 B를 제외한 연결된 노드의 개수 와

B에서는 A를 제외한 연결된 노드의 개수 를

곱한다. (두 노드를 중심으로 나올 수 있는 모든 경우의 수를 고려할 수 있으므로)

다만 ㄷ을 구할 때 주의할 점은 출발 노드(A)에서 다른 노드(B)들을 모두 계산했다면 A는 더 이상 다른 노드(B)도 될 자격이 없기 때문에(이미 다 계산해 주었음) boolean 배열을 통해 체크해주어 이후에 더 이상 계산하지 않도록 한다.

★소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static ArrayList adj[]; public static void main(String[] args) throws IOException { int n = Integer.parseInt(br.readLine()); adj = new ArrayList[n + 1]; for(int i = 1; i<=n; i++) { adj[i] = new ArrayList<>(); } for(int i = 0; i= 3) { sumG += (x*(x-1)*(x-2))/6; } } boolean visited[] = new boolean[n + 1]; // ㄷ for(int i = 1; i<=n; i++) { for(int j = 0; j sumD) { bw.write("G"); }else if(sumG * 3 < sumD) { bw.write("D"); }else{ bw.write("DUDUDUNGA"); } bw.flush(); } }

from http://sweet-smell.tistory.com/35 by ccl(A) rewrite - 2021-08-22 01:59:44