본문 바로가기

전체 글103

BOJ17471_게리멘더링 JAVA 우선 조합으로 각 지역의 그룹을 짓고 그 그룹들이 서로 모두 연결이 가능한지를 체크하면 되는 문제였다. 지금까지 못풀었던 이유는 단순히 연결성 체크까지는 잘 짰는데 연결이 안되어 있으면 제외하는 조건을 잘못 짬.. 단, 이때 주의할점은 조합을 할 때 예를들어 6C1과 6C5의 결과는 사실상 같기 때문에 지역구의수/2 만큼만 조합을 하면 된다. import java.io.*; import java.util.*; class Group{ int groupNum; ArrayList connects = new ArrayList(); Group(int groupNum){ this.groupNum=groupNum; } } public class Main { static Deque choice = new ArrayDe.. 2020. 11. 12.
백준 14267번 내리 칭찬 java 자신의 직속 상사 순서대로 연결을 하면 내리 칭찬이기 때문에 트리 형태가 나타나게 된다. 자신을 칭찬하는 숫자를 연결된 트리의 자식으로 쭉쭉 내리면 된다. 이번엔 시간 초과가 발생함....//해결 방법은 아래 시간초과가 발생할 수 있었던 부분은 바로 한쪽으로 편향된 트리인데 편향된 트리에서 최종보스 바로 밑에 있는 부하에게 칭찬(또는 갈굼)을 계속적으로 하는 경우이다. 그럴 경우 굉장히 깊이 있는 트리 끝까지 방문해야 하기 때문에 시간초과가 났던것이다. 예를들어 깊이가 100000인 트리에서 2번 직원에게만 100000번의 칭찬을 한다고 가정하면 트리노드를 방문하는 숫자는 100000*100000 이기때문에 10,000,000,000번 즉 100억번을 방문해야 하며, 이것은 1초에 1억번 계산하는 컴퓨터.. 2020. 11. 12.
백준 14502번 연구실 JAVA 빈공간과 바이러스의 위치를 모두 저장한다. 빈공간중 조합을 통해 3개의 빈공간을 선택한다. 3개의 벽을 새운뒤 BFS를 통해 바이러스를 퍼트리고 안전공간의 개수를 샌다. 모든 조합에 대해서 반복한 후 안전공간이 최대가 되는 숫자를 출력한다. 기본적으로 DFS(백트래킹)를 이용한 조합 함수와 바이러스를 퍼트릴때에 BFS를 사용함으로서 풀 수있는 문제였다. import java.io.*; import java.util.*; class Point{ int x; int y; Point(int x, int y){ this.x=x; this.y=y; } } public class Main { static ArrayList virus=new ArrayList(); static ArrayList empty=new Ar.. 2020. 11. 9.
백준 15686 치킨배달 JAVA import java.io.; import java.util.; class shop{ int x; int y; shop(int x, int y){ this.x=x; this.y=y; } } public class Main { static ArrayList choiceshops; static int checkDistance(List homeList,List shopList){ int total=0; for(int i=0;i 2020. 11. 5.

티스토리툴바