potato's devlog

💁🏻 문제링크 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 💻 문제 풀이 이런 문제를 만나면, 현재위치에서 위, 아래, 오른쪽, 왼쪽을 살펴보면서 연결이 되어있나? 를 판단해야한다. 위 그림을 보면, 현재 위치는 (0,0)일때 방향키로 움직일 수 있다. x좌표인 0에다가 dx[2]을 더하고, y에다가 dy[2]을 더해주면, (1,0)으로 한칸 아래로 이동할 것이다. 이처럼 이렇게 "연결된 1을 찾아 무언가를 찾는문제"라면, 이렇게 방향키를 생..

문제링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 IDEA 우선, 문제를 읽어보면 조건이 세개 나 달려있지만, 다 같은 말이다. 그저 집의 색상은 앞뒤 집과 겹치지 않아야 한다는 하나의 조건일 뿐인 것이다. 1번집이 빨간색이면, 2번집은 파랑이나 초록이면 되고, 50번째 집이 빨강이라면, 49번집과 51번집은 빨강이 아니면 된다. 나는 이문제를 보고 바로 이 문제(click!!)를 풀었던 경험을 생각했다. 마지..

문제 링크 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 idea 아니 풀다보니, 1,2,3 더하기 관련한 시리즈 문제를 몇개 풀어봤으므로, 더 복잡해야되는데 이게 규칙이라고? 하면서 애매모호하게 풀었던 문제였다. 근데 아니나 다를까 1,2,3더하기 (백준 9095번) 문제랑 그냥 동일한 문제였다. ㅋㅋㅋㅋ 괜히 쫄았네... https://didu-story.tistory.com/225 [백준] (Swift) 9095번 - 1,2,3 더하기 (스위프트 다이나믹 프로그래밍 풀이) 문제 링크..

문제 링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA 규칙을 찾다가 2차원배열로 풀어야한다는 생각을 미처 하지 못해서 인터넷을 참고했다. dp 도 다양한 유형을 풀며 어떤 상황일 경우 어떻게 접근해야하는지 감을 익혀야하는 것 같다. 규칙찾기가 힘들었다. 이런 문제가 나오면 2차원으로 풀자. k개를 더해서 n을 만드는 경우의 수를 배열로 넣으면 된다. 2차원 배열일 경우 표를 그리면서 규칙을 찾아나서면 된다. 생각보다 간단한 규칙이 있다. dp는 무조건 규칙부터! 규칙을 설명해보겠다. 우선 위에서 적은것 처럼 k개의 수를 더해서 n을 만들자! 라는 맥락..