분류 전체보기(90)
-
BOJ 5573 : 산책
https://www.acmicpc.net/problem/5573 여학 때 풀지 못해서 업솔빙을 한 문제이다. 우리는 K번 후 각 위치에 대해 몇 번 방문했느냐에 따라 다음 방향이 달라짐을 관찰 할 수 있다. 이를 dp로 구하면 된다. dp[i][j] = (i,j)를 몇 번 지나갔는가? dp[1][1]은 초기 위치에서 몇 번 지나갔는가를 물으므로 k-1일테고, 식은 dp[i+1][j] = dp[i][j]/2 + (dp[i][j]%2(i,j에서의 초기 방향이랑 다른가) & !a[i][j](초기방향이 아래))(오른쪽으로 갈 때) dp[i][j+1] = dp[i][j]/2 + (dp[i][j]%2(i,j에서의 초기 방향이랑 다른가) & a[i][j](초기방향이 오른쪽))(아래로 갈 때) . 이를 구하고 답을 ..
2021.11.16 -
BOJ 13361 : 최고인 대장장이 토르비욘
https://www.acmicpc.net/problem/13361 13361번: 최고인 대장장이 토르비욘 전성기 시절의 오버워치는 지구 상에서 가장 진보된 최첨단 무기를 보유했으며, 그 무기의 출처는 바로 토르비욘 린드홀름이라는 전무후무한 기술자의 작업장이었다. 하지만 이런 토르비욘에 www.acmicpc.net 여학 때 못 풀어서 1달 동안 힌트 + 생각해보고 푼 문제이다. 유니온 파인드로 서로 길이가 같은 것끼리 묶어주고, 이중 전체 변 길이의 합에서 서로 다른 (그룹에 있는 것들의 갯수)개의 길이를 빼면 된다. 풀이 자체는 아주 간다하지만, 정말이지 사람이 이걸 어캐 생각할 수 있는지 모르겠다. 코드
2021.11.15 -
BOJ 2500 : 복불복
https://www.acmicpc.net/problem/2500 2500번: 복불복 첫째 줄에 3개의 정수 N, K, T가 빈칸을 사이에 두고 주어진다. N은 회전판을 돌리는 횟수를 나타내고, K는 게임을 하는 사람에게 처음 주어지는 조약돌의 개수를 나타낸다. T는 회전판에 그려져 있 www.acmicpc.net 상당히 어렵고 재밌는 발상의 문제이다. 회전판을 한 번 돌렸을 때 i개의 돌을 가져갈 때의 가능한 경우의 수를 C_i라고 하면 C_0 + C_1*x + C_2*x^2 + ........ C_k*x^k 라는 다항식을 만들 수 있다. 이때 x^i에서의 i는 쓴 돌의 갯수라고 생각하면 이해가 편하다. 그렇다면 N번 회전판을 돌렸을때는 이렇게 표현할 수 있다. (C_0 + C_1*x + C_2*x^2..
2021.08.17 -
BOJ 17353 : 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별
https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 재밌는 문제이다. 우리는 느낌상 레이지 세그를 생각할 수 있지만, 더하는 값이 등차수열이기에 어떻게 해야할지 고민해봐야 한다. 이때, 우리는 인접한 두 배열 원소의 차이를 세그트리 원소로 하여 생각해보면, 결국 등차수열로 더하는게 어떤 구간 전체에 1을 더하는 것이랑 동치가 된다. 이때 두 원소의 차이를 저장하는 세그먼트 트리이기 때문에 구간의 마지막 원소를..
2021.08.17 -
BOJ 1023 : 올바른 괄호
https://www.acmicpc.net/problem/1023 1023번: 괄호 문자열 괄호 문자열은 다음과 같이 정의 한다. 빈 문자열은 괄호 문자열이다. S가 괄호 문자열일 때, (S)도 괄호 문자열이다. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다. 모든 괄호 문자열은 위의 www.acmicpc.net 를 먼저 풀고 오는걸 추천한다. 17428번: K번째 괄호 문자열 첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다. www.acmicpc.net dp[a][b][c] = 크기 a, b='('갯수 - ')'갯수, b c라고 할때, 만들 수 있는 괄호 ㄴㄴ 문자열의 갯수 b
2021.08.17 -
BOJ 17428 : K번째 괄호 문자열
https://www.acmicpc.net/problem/17428 17428번: K번째 괄호 문자열 첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다. www.acmicpc.net 걍 dp문제인데 재밌다. dp[i][j] = 길이가 i이고, 완성되지 않은 괄호쌍이 j개일 때 만들 수 있는 괄호쌍 갯수 dp[i][j] = dp[i+1][j+1] ('('를 넣을 때) + dp[i+1][j-1] (')'를 넣을 때) 문자열 구하는건 간단하다. "'('를 넣을 때"와 "')'를 넣을 때"를 분리해서 K번째 문자열을 구해주면 된다. 코드
2021.08.14