Heecheol's blog

문제 https://www.acmicpc.net/problem/25330 25330번: SHOW ME THE DUNGEON 올 여름 출시된 RPG 게임 "SHOW ME THE DUNGEON"은 주인공 시루가 몬스터에게 침략당한 마을을 구하는 내용의 게임이다. 배경이 되는 나라는 $0, 1, 2, \cdots, N$번의 번호가 붙어있는 $N+1$개의 마을로 이루 www.acmicpc.net 풀이 처음에 DFS를 이용해 배열의 크기가 1인 것부터 n개인 것까지 미리 모두 구한 뒤에 각각의 케이스별로 계산해서 결과를 구했었다. 이렇게 했을때 시간 초과가 나와서 방법을 더 고민하다가 배열에서 k보다 큰 것들은 미리 빼놓으면 dfs를 돌릴때 많이 줄어들 수도 있다고 생각해서 다시 시도해봤는데 역시 큰 차이가 없어..

문제 https://www.acmicpc.net/problem/24954 24954번: 물약 구매 동전 10개를 지불하고 1번 물약을 구매하면, 3번 물약이 동전 10개만큼 할인되어 값이 동전 10개가 된다. 2번 물약은 동전 20개만큼 할인되어야 하지만, 최소 1개는 지불해야 하므로 값이 동전 1개가 www.acmicpc.net 풀이 스위프트로 푼 사람이 나밖에 없어 좋은 풀이인지는 잘 모르겠다. 모든 경우를 다 따져봐야 가장 싸게 살 수 있는 방법을 알 것 같았다. 우선, 입력을 받으면서 다른 물약을 할인시키는 물약의 인덱스를 discount에 넣고, 아닌 물약들은 noDiscount에 넣어주었다. 이때, 다른 물약을 할인시키는 정보도 info라는 변수에 인덱스별로 넣어주었다. 다음으로 dfs를 이용..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 이 문제는 상하좌우가 아니라 8방향으로 갈 수 있기때문에 dx dy를 1,-1만 생각하지 않고 1,2,-1,-2를 생각해주면 된다. BFS를 이용해서 풀었다. 시작점을 큐에 넣어준 뒤, 8방향에 대해 각각 조건을 만족한다면 이전 값에 1을 더해주어 chess[newX][newY]에 넣어주었다. 이때, newX와 newY가 target과 같다면 결과를 출력하고 반복문을 탈출하였다. 처음에는..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 색약인 사람과 색약이 아닌 사람의 답을 한 번에 구할 수 없다고 생각하여 두 번에 나눠서 구했다. BFS로 해결했기때문에 이전의 BFS문제의 풀이 방법과 거의 동일하게 구현하였다. removeAll()메서드의 시간복잡도가 O(N)인 것을 알게되어 하나의 큐를 써서 removeAll()한 뒤에 다음 반복문을 돌리는 것이 아닌 각각의 큐를 만들어주었다. 또한 idx를 이용해 queu..

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 일반적인 BFS문제였다. 우선, ground라는 변수를 만들어 배추가 어디에 있는지 표시를 한다. 이 배추들을 차례대로 반복문을 통해 방문할텐데 방문했다는 표시를 하기 위해 visited변수를 만들어주었다. 이제 반복문을 돌다가 1(배추)를 만나면 그 자리에서 BFS를 돌린다. 지렁이는 인접한 배추끼린 하나만 필요하므로 해당 배추 주변을 상하좌우로 확인하면서 방문하지 않은 1인 경우엔 큐에 넣어 다..