본문 바로가기

BOJ128

BOJ 2981: 검문 문제 링크 입력으로 들어올 수 있는 숫자의 최댓값이 10억임을 확인했지만 혹시나 싶어서 M = 2..min 까지 해봤지만 역시 틀렸었다. 근데 제출 결과가 틀렸습니다가 나온 걸 봐선 그냥 내 풀이 자체가 틀렸을 수도 있겠다. 이 문제는 위와 같은 이유로 다른 방법을 생각해야 하고 그 방법은 GCD를 활용하는 것이다. 입력이 5, 17, 23, 14, 83이면 가능한 M=3인데 입력을 다시 M과 엮어서 표현하면 5=1*3+2, 17=5*3+2, 23=7*3+2, 14=4*3+2, 83=27*3+2이다. 몫 부분을 제외하면 M과 R(나머지)은 공통되게 갖고 있는 것을 확인할 수 있다. 이 문제에서 기억해야 할 트릭은 나머지를 지우는 것이다. 예를 들어 17-5를 계산해보면 (5*3+2)-(1*3+2) = 4.. 2022. 5. 19.
[BOJ] 15553번: 난로 문제 링크 2018년 JOI 1번 문제다. 난로가 켜져 있는 시간은 N + α 인 것은 자명하다. 그렇다면 α를 알아야 한다. 성냥이 N보다 부족하면 계속 켜놔야 하는 시간을 알아야 하는데 예제를 보면서 계산하는 것이 좀 더 좋을 것 같다. [예시1] 1 3 6 K가 2일 땐 1 3 사이[1초]나 3 6 사이[2초]를 계속 틀어놔야 할 것이다. 이것에 착안해서 나는 우선순위 큐(오름차순 정렬)를 사용해서 (친구들 방문이 이어져 있지 않을 경우) 일 때 간격을 우선순위 큐에 저장을 시키고, 만약 이어져 있는 경우에는 cnt를 증가시켰다. 그래서 우선순위 큐에서 pop을 시키는 횟수는 가 된다. 난로가 켜져 있는 시간의 최솟값을 구해야 하므로 정답은 이 된다. #include using namespace s.. 2018. 9. 30.
[BOJ] 2842번: 집배원 한상덕 2842번: 집배원 한상덕 이분 탐색 + flood-fill도 가능하지만 inchworm 알고리즘을 사용할 수도 있다. 피로도와 방문할 수 있는 곳은 비례하기 때문이다. (찾아보니 단조함수이면 가능하다고 한다.) inchworm 알고리즘에서는 1차원으로 작업을 하는데 고차원에서도 가능한지는 모르겠다만... 아무튼 1차원에서 작업하기 때문에 2차원의 좌표에 있는 값을 1차원의 위치로 바꿔주고 정렬을 한 상태에서 inchworm 알고리즘을 돌면서 flood-fill을 했다. #include #include using namespace std; const int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, dy[] = { 1, 0, -1, -1, -1, 0, 1, 1 }; int n, .. 2018. 9. 13.
[BOJ] 1309번: 동물원 1309번: 동물원 지극히 개인적인 생각입니다. 제대로된 풀이는 다른 블로그 보시길 바랄게요 죄송합니다! 문제가 규칙성을 찾을 수 있을 것 같아서 야매로 찾다가 3 7 17 41이 나오길래 int n, ret = 3; scanf("%d", &n); int plus = 4, add = 6; for (int i = 1; i < n; ++i) { ret += plus, ret %= R; plus += add, add += 8; } 했지만 당연히 틀렸다. 그래서 "스티커"문제의 경험을 되살려서 대각선으로만 놓을 수 있다는 것에 착안을 했다. dp[0][i] = dp[1][i - 1] + dp[0][i - 2] + dp[1][i - 2] dp[1][i] = dp[0][i - 1] + dp[0][i - 2] + d.. 2018. 8. 31.
[BOJ] 1699번: 제곱수의 합 1699번: 제곱수의 합 해법 DP, 동전2 문제와 굉장히 유사하다. 분명히 정올 준비를 하면서 이 문제를 풀어 봤음에도 불구하고 처음에는 n보다 작으면서 가장 가까운 제곱수를 빼주는 것으로 생각했는데 그렇게 하니까 32 = 16 + 16같은 반례에 막혔다.(당연하다... ㅠ) 그래서 다시 생각한 것이 제곱수들의 리스트가 주어질 때 i를 범위 내의 제곱수들로 뺀 수의 최소 구성 개수 중에서 가장 작은 것을 고르는 것으로 생각했다.(= min(D[i - sqrt_list[j]]) ) 그래서 나온 점화식은 다음과 같다. int Min = dp[i - sqrt_list[0]]; for (int j = 1; j 0) return dp[n]; int idx = find_close(n); dp[n] = 1 + st.. 2018. 8. 30.
[BOJ] 9465번: 스티커 9465번: 스티커 해법 처음 내가 접근했던 방법은 그냥 무식하게 대각선으로만 생각하고 풀었다. 그래서 당연히 틀렸고 친구와 다른 분들의 도움을 받아서 이 문제를 풀게 됐다. 우선 이 문제는 DP이고 DP식은 dp[i][j]: i열,j행까지의 스티커의 최대값이다. 하나를 선택하면 상하좌우를 선택하지 못하기 때문에 기본적으로 이동은 대각선으로만 가능하다. 그래서 DP식을 대각선쪽만 생각해서 짜면 절대 안된다. 이렇게 한다면 250이 최대가 되어서 정답인 260이 아니게 된다. 즉 한 칸을 건너뛰어야 한다. 그러면 두 칸을 건너뛰는 것은 어떨까..? 결론부터 말하자면 손해다. 두 칸을 뛰게 되면 한 칸씩 대각선 건너는 것과 같은 지점을 가지만 거치는 것은 더 적으므로 항상 손해일 수 밖에 없다. 그래서 점화.. 2018. 8. 30.
[BOJ] 1654번: 랜선 자르기 https://www.acmicpc.net/problem/1654 랜선 하나의 길이를 이분탐색하자. #include #include using namespace std; int k, n, lan[1000001], Max = -987654321; int main() { scanf("%d %d", &k, &n); for (int i = 0; i 1; int cnt = 0; for (int i = 0; i = n) .. 2018. 8. 9.
[BOJ] 2805번: 나무 자르기 https://www.acmicpc.net/problem/2805 나무를 자르는 것을 이분 탐색으로 구할 수 있다. 1부터 주어진 나무의 최대 길이까지 이분 탐색을 하면서 잘라서 얻은 나무가 더 많으면 위 부분으로 조절하면 되고 반대로도 같은 방식으로 하면 된다. 하지만 그 필요한 양만큼만 못 가져갈 때도 있으므로 그럴땐 한 번 더 mid를 구한 것이 답이다. 참고: 파라매트릭 서치 #include #include using namespace std; int n, m, maxH = -987654321, tree[1000001]; int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) { scanf("%d", &tree[i]); maxH = ma.. 2018. 8. 9.
[BOJ] 10815번: 숫자 카드 https://www.acmicpc.net/problem/10815 이분 탐색 #include #include using namespace std; int n, m, ar[500001]; bool bs(int find) { int s = 0, f = n - 1; while (s find) f = mid - 1; else s = mid + 1; } return 0; } int main() { scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &ar[i]); sort(ar, ar + n); scanf("%d", &m); while (m--) { int a; scanf("%d", &a); printf("%d ", bs(a)); } return 0; } 2018. 8. 9.
[BOJ] 1162번: 도로포장 https://www.acmicpc.net/problem/1162 벽 부수기 문제와 비슷하다. 주어만 바뀐 느낌이고 트리 구조(?)에서 그래프로 바뀐 것 뿐이다. 도로를 포장하거나 안 하거나 두 가지 경우가 있으므로 그 두 가지 경우를 모두 확인해주면 된다. #include #include #include #include #include using namespace std; struct Edg { int idx, cnt; long long dst; Edg(int idx, long long dst) : idx(idx), dst(dst) {} Edg(int idx, long long dst, int cnt) : idx(idx), dst(dst), cnt(cnt) {} bool operator nxt.dst .. 2018. 8. 7.
[BOJ] 10545번: 뚜기뚜기메뚜기 https://www.acmicpc.net/problem/10545 만약에 map이 없었다면... 이걸 어떻게 풀었을까 STL을 만들어 주신 모든 분에게 감사드립니다. #include using namespace std; const char alphabet[10][5] = { {}, {}, {"abc"}, {"def"}, {"ghi"}, {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"} }; int main() { ios_base::sync_with_stdio(false), cin.tie(0); string str; map m; for (int i = 1, a; i > a; for (int j = 0; alphabet[a][j]; ++j) m[al.. 2018. 8. 7.
[BOJ] 2698번: 인접한 비트의 개수 https://www.acmicpc.net/problem/2698 D[n][k][lb]: 길이가 n이고 연속된 비트가 k개이면서 마지막 비트가 lb(0 또는 1)인 수열의 개수 처음에는 D[n][k]으로만 점화식을 세워보려고 했는데 끄적끄적하다 보니 결국에는 마지막 비트와 관계가 있어서 어쩔 수 없이 사용하게 되었다. 마지막 비트가 0일 때 D[n][k][lb] = D[n - 1][k][0] + D[n - 1][k][1] 마지막 비트가 0인데 길이는 n이고 연속된 비트가 k인 수열의 개수는 길이 n-1짜리에서 마지막 비트가 0, 1인 두 개의 수를 합치면 된다. ex) 11100, 01110 -> 1110에서 0하나 붙이면 되고, 0111에서 0하나 붙이면 된다. 마지막 비트가 1일 때 D[n][k][l.. 2018. 8. 7.
[BOJ] 11779번: 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 다익스트라를 구현하는데 경로를 저장해야 한다. 추적방법 trace 배열을 선언한다. 다익스트라 알고리즘에서 거리 업데이트하는 부분에 trace[nxt.idx] = now.idx로 지정한다. 도착 지점부터 trace 배열을 돌면서 t = trace[t]를 통해 노드 A로 오기 전 노드로 t를 변경한다. #include using namespace std; struct Edg { int idx, fair; Edg(int i, int f) : idx(i), fair(f) {} bool operator nxt.fair + now.fair) { dist[nxt.idx] = nxt.fair + now.fair; trace[nxt.idx] = now.. 2018. 8. 7.
[BOJ] 14442번: 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 전형적인 BFS에 벽 부술 수 있는 조건을 붙인 문제이다. 보통 이런 문제들은 visit 배열을 visit[x][y][cnt]로 정의해서 구할 수 있다. 이런 건 코드를 보면서 할 게 나을 것 같다. if (Map[nxtX][nxtY] == '0' && vst[nxtX][nxtY][now.cnt] == INF) { vst[nxtX][nxtY][now.cnt] = vst[now.x][now.y][now.cnt] + 1; Q.push({ nxtX, nxtY, now.cnt }); } else if (now.cnt + 1 nxtX || nxtX >= N || 0 > nxtY || nxtY >= M) continue; if (Map[nxtX][.. 2018. 8. 7.
[BOJ] 1727번: 커플 만들기 https://www.acmicpc.net/problem/1727 남자를 기준으로 잡고 풀었다. D[i][j]: i번째 남자까지와 j번째 여자까지 짝을 맺었을 때 성격 차이의 최소합 D[i][j] = D[i - 1][j - 1] + abs(man[i] - girl[i]) if(i > j) D[i][j] = D[i - 1][j] - 남자가 여자보다 많아서 짝을 지을 수 없음 if(i 사실 이렇게 생각하는게 맞는지 모르겠다. 어쨋거나 핵심인 짝을 만들거나, 만들지 않거나를 점화식으로 세운 것이다. 저 세 식 중 최소인 값을 D[i][j]의 값으로 업데이트한다. 또한 남녀 입력 받은 수열을 정렬해줘야 하는데 그.. 2018. 8. 4.

티스토리툴바