Heecheol's blog

문제 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인 경우엔 큐에 넣어 다..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 이용해 하나의 수에서 -1한 값, +1한 값, *2한 값을 각각 조건을 확인해준 후, 큐에 넣고 확인하는 것을 반복해주었다. 100001크기의 배열을 선언해서 구현하였따. 처음에 수빈이가 있는 queue[5]를 0으로 초기화하고, +1, -1, *2한 값들에 대해서 배열의 해당 위치가 -1인지 확인 후에 아니라면 이전 값에 +1을 하여 queue[ta..