potato's devlog

🟠 문제링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 🟠 문제 풀이 아이디어 가장 기초적인 dp 문제중 하나였다. 하지만 가장 중요한것은, 생각을 반대로해야한다는 것이었다. "처음부터 계단을 어떻게 올라가지?" 생각보다는, "최종 도착지기준으로 봤을때, 어디서 올라왓찌?"를 고려해봐야한다는 것이다. 연속으로 3칸의 계단을 밟을 수가 없기 때문에, 도착지 기준으로 올라올 수 있는 방법은 아래 그림처럼 딱 두가지 방법이다. 이렇게 dp 점화식을 유도해냈..

✅ 문제 링크 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net ✅ 문제 풀이 아이디어 문제가 굉장히 난해하게 생겼기 때문에 ,,,, 처음엔 BFS 문제인지 감이 안잡혔다. 인터넷을 찾아보니, 이 문제의 핵심은 다음과 같았다. 가운데 구멍뚫린 부분은 신경쓰지 않아도 된다. 어차피 BFS 로 탐색을 (0,0)부터 시작하게되면, 구멍으로 접근이 불가능하다. 외부 공기자리부터 탐색을 시작하면 어차피 구멍 내부로 접근할 수 없기떄문!! 가장자리는 항상 외부공기로 둘러쌓여있..

✅ 문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net ✅ 문제 풀이 아이디어 기본적으로 연합국가인지 아닌지를 판단해야하기 때문에 BFS로 풀어야한다고 생각했다. 위의 출력예제를 보면, 점선이 생기는 위치가 다르다. 30과 40은 직접적인 연결은 아니지만, 어쨋든 연합국가이긴하다. 그렇기 때문에 초반에 어렵게만 생각되었던 "어디에 점선이생기는지 고려해야하는가"를 전혀 생각하지 않고 그냥 탐색하면서 연합국가에 같이 담아주면된..

문제링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 풀이 좌우/상하 로 인접한 사탕을 바꿀 수 있다. 표[1]과 같이 사탕이 주어졌다. 여기서 [0][0] 사탕과 [0][1] 사탕을 바꾸어보자. 표[2] 와 같은 결과가 나온다. 이렇게 되면 행끼리 인접한 사탕의 최고 개수는 2, 열끼리 인접한 사탕의 개수는 3이 된다. 다시 표[1]로 돌아가서 표[1]에서 [0][0] 사탕과 [1][0] 사탕을 바꾸어보자. 표3을 보면, 행끼리 인접한 사탕 최고 개수는 2개, 열끼리 인접한 사탕 최고 개수는 1개 이다. 이 위의 과정을 for 문을 통해서 반복해주었다. 그..

문제 링크 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 내가 푼 풀이 태그로 구별해야하는 문제인것은 알았지만 while문과 if 문을 중첩해서 새로운 array에 넣어주면서 문제를 풀려고했다. 메모리를 너무 많이 차지할 것 같다. 고민해보다가 인터넷을 조금 찾아보니 일반 string으로 더해주고, 초기화해주고, print(terminator) 기능을 이용해서 한줄로 출력할 수 있었다. terminator 기능..