백준177 [Swift][DP] 백준 11057번 (오르막 수) 요구능력 : DP에 대한 이해 코드설명 : 수의 길이에 따른 오르막 수의 개수를 세는 문제이다. 오르막수는 오름차순과 비슷한데 같은 수가나와도 오르막수가 된다. 예를들면 1 2 3, 1 2 2은 오르막 수 인데, 1 2 1, 1 2 0은 오르막수가 아니다. 이 문제에서 주의깊게 봐야할 점은 004 이런것도 다 세줘야하는것이다. 수는 0으로 시작할 수 있다는게 이런의미. 수를 관리하기위한 문제는 2차원 배열을 생각하는게 좋다. 수의 끝을 기준으로 DP구하기가 수월하기 때문이다. DP[1][0]은 1자리수에 끝자리 수가 0으로 끝나는것이다. DP[3][5]는 3자리수에 끝자리 수가 5로 끝나는 것이다. DP[1][0]부터 DP[1][9]까지는 1을 삽입해준다. DP[1][0]은 1자리에 끝이 0으로 끝나는.. 2021. 11. 5. [Swift][BruteForce] 백준 15661번 (링크와 스타트) 요구능력 : 백트래킹에 대한 이해 코드설명 : 스타트와 링크와 문제가 조금 다르긴하지만 똑같은 방식으로 풀었는데, 맞았다. 설명이 필요하신분은 스타트와 링크를 봐주세요. 스타트와 링크와 다른점은 이 문제에는 N이 홀수로도 들어온다는 것이다. 스타트와 링크 코드를 링크와 스타트에 넣으면 틀렸다고 나오는데.. 이유는 모르겠고 똑같이 풀어도 맞을 수 밖에 없는 이유를 적어보자면, 두팀의 능력치를 빼서 작은값이 나오는 경우는 두 팀이 그래도 인원수가 비슷한경우에 이루어진다. 만약 5명이라면, 2명 3명 이런식이다. 그래서 depth가 n/2인 경우에 멈춰도 되는거다. 후기 : 막 어려운건 아니지만, visited가아니고 딴 배열에 저장해서 찾느라 시간 좀 걸렸다. let n = Int(String(readLin.. 2021. 11. 5. [Swift][DP] 백준 1303번 (동물원) 요구능력 : DP에 대한 이해 코드설명 : 2xn의 사각형이 있을때, 사자가 가로, 세로방향으로 있으면 안된다. 사자가 있을 수 있는 경우의수는 왼쪽, 오른쪽, 그리고 아예없을 경우이다. 이 문제는 사자를 배치하는 모든 경우의수를 구하는 문제이다. 점화식을 만들어보자. dp[i]를 구하려는데 i번째 배열에는 사자가 없을 수도 있다. 사자가 없는경우에는 이전 인덱스인 i - 1에서는 왼쪽에 사자가 있을 수도 있고 오른쪽에 사자가 없을 수도 있고 사자가 아예 없을 수도 있다. 이 문제는 사자를 배치할 수 있는 모든 경우의수를 구하는 것이므로, 조건별로 경우의수를 다 구해준다. 각각 다른 조건을 만족하는 경우의수들을 구하기 위해서는 dp를 2차원 배열로 사용해야한다. dp[i][0] = (dp[i - 1][1.. 2021. 11. 4. [Swift][DP] 백준 1149번 (RGB거리) 요구능력 : DP에 대한 이해 코드설명 : 26 40 83 39 60 57 13 89 99 문제를 보면 앞뒤에 나온 컬러는 사용할 수가 없다. 우선 조건없는 점화식을 만들어보자. 조건이 없다면 최소값을 누적하는 dp이다. 그렇다면 dp[i] = dp[i - 1] + arr[i][최소가되는부분] 이 만들어진다. dp[i - 1]에는 이미 최소값이 만들어진것이라 가정한것이다. 조건을 넣은 점화식을 만들어보자. 우선 조건은 3가지가 있다. R일때, G일때, B일때. dp[i]가 R이면 이전에는 G와 B가 나와야한다. 아래 코드에서는 R이 0, G가 1, B가 2 이다. dp[i]를 R로 칠한경우의 DP가 있을것이고, G로 칠한경우의 DP가 있을것이고, B로 칠한경우의 DP가 있을것이다. 그러므로 arr배열에 .. 2021. 11. 4. 이전 1 ··· 20 21 22 23 24 25 26 ··· 45 다음