SWEA
-
[SWEA 3234 - 준환이의 양팔저울]Algorithm 2020. 11. 9. 18:27
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. DFS를 이용하여 순열을 구현하는 문제다. 나는 올리는 과정에서도 오른쪽이 왼쪽보다 무게가 적어야 한다는 것을 생각하지 못해서 2번정도 fail했다. DP를 이용하지 않고 순열로 구현했기 때문에, StringBuilder와 매개 변수로 전달해주어야 시간 초과가 나지 않는다. 풀이 방법 dfs를 이용해서 순열을 구현한다. 아래 두가지 경..
-
[SWEA 4193 - JAVA] 수영대회 결승전Algorithm 2020. 11. 9. 18:25
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성이를 우승시키기위한 최단 경로의 시간을 출력하자! 신호등 문제로 BFS에 현재시간과 소용돌이를 건널 수 있는 시간을 비교해서 큐에 넣어준다. 소용돌이의 시간이 일정하기 때문에 신호등이나 견우와직녀보다는 비교적 쉬운 문제다. 풀이 방법 시작점을 큐에 넣어준다. 큐 사이즈를 받아서 사이즈 만큼 돌아준다 (시간 체크) 소용돌이를 만날 경우 건널 수 없으면 다시 큐에 넣어준다. 2번을 체크해서 BFS를 구현할 경우 visit배열을 int형으로 해줄 필요가 없다 (메모이제이션 불필요) import java.io.*; import java.util.*; public cl..
-
[SWEA 4727 - JAVA] 견우와 직녀Algorithm 2020. 11. 9. 18:12
SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 견우가 까마귀와 까치의 도움으로 최대한 빠르게 직녀에게 가는 방법을 찾아내자! BFS에 여러가지 조건을 적용한 문제로, 예전에 풀었던 신호등과 비슷한 문제다. 신호등은 추후에 업로드시 링크를 달아야겠다! 문제를 읽기가 힘들고, 조건을 이해하는게 힘들었다…. 풀이 방법 BFS를 돌면서 아래의 조건을 만족시킨다. 방문처리는 메모이제이션으로 가장 짧은 시간을 저장하여 확인한다. 오작교는 시간이 T라면 T의 배수에 건널 수 있다. 견우는 절벽을 연속으로 건널 수 없다. 교차하는 곳에는 오작교를 만들 수 없다. 0인 곳 (M인 오작교)는 한 개만 만들 수 있다. impor..