2JINISHAPPY 2JINISHAPPY

https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 이분탐색 + DFS로 풀거나 다익스트라로 풀 수 있는 문제 나는 다익스트라로 풀다가 계속 맞왜틀 발생해서 그냥 이분탐색 + DFS로 풀었당 ㅎㅎ #include #include #include #include #define ll long long using namespace std; int map[1001][1001], dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, n; bool visit[1001][1001]; bool safe(int x, int y) { return x >= 0 &..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 현재 볼륨이 범위에 적합하지 않는 경우(불가능)일 때와, 아직 계산하지 않은 경우(가능 여부 모름)일 때를 분리해주어야 한다는 걸 시간초과 덕분에 알았다 #include #include using namespace std; int n, s, m; int v[101], cache[101][1001]; int dp(int cur, int dep) { if (cur..

https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 값의 범위를 신경써야 하는 다익스트라 문제 정점은 10000개라서 인접행렬을 만들 시 10000*10000=1억개 * 4byte의 메모리가 필요한데 간선이 최대 10만개 들어오므로 꼭 인접리스트로 처리해야 한다 #include #include #include #define ull unsigned long long #defin..

https://www.acmicpc.net/problem/22114 22114번: 창영이와 점프 창영이는 버스에서 내린 뒤 회사로 걸어가고 있다. 창영이가 걸어가는 길은 대부분 회색 보도블럭으로 포장되어 있는데, 가끔씩 빨간 보도블럭이 놓여있을 때가 있다. 창영이는 어린 시절 빨간 www.acmicpc.net 오랜만에 푸는 DP문제 처음에 bottom-up으로 풀려고 했는데 점화식이 계속 생각이 안 나서 재귀로 푼 다음에 메모이제이션 적용했다 dp도 재귀(top-down)이기 때문에 base case, inductive step, memoization 이 세 가지 위주로 설계해야 할 듯 #include #include using namespace std; int n, k, l[100005], dp[2][..

https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 특정 좌표에서 BFS또는 DFS를 시행하여 같은 숫자인 칸을 전부 업데이트 시킨 뒤 주어진 배열과 같은지 검사하면 되는 간단한 BFS 문제 import sys from collections import deque def bfs(r, c, num): global origin, after, n, m dx=[1,0,-1,0] dy=[0,1,0,-1] visit..

https://www.acmicpc.net/problem/20304 20304번: 비밀번호 제작 서강대학교 전산실에서 보안직원으로 일하는 향빈이는 한 통의 이메일을 받게 되었다. 이메일에는 서버 관리자 계정에 대한 비정상적인 로그인 시도가 감지되었다는 내용이 적혀 있었고, 첨부 www.acmicpc.net 익숙한 문제? ㅎㅎ 틀린문제 리스트에 있는게 싫어서 오랜만에 다시 풀어봤다 아주 훌륭한 문제였다 ( = 어렵다는 뜻 ) 안전거리와 안전도가 등장하는데 안전거리를 구하는 것 자체는 XOR 풀이가 직관적으로 떠오를 수 있지만 비밀번호 후보를 찾는 데에 Bitmask + BFS를 바로 떠올리기는 쉽지 않다 항상 특별한 분류의 알고리즘 문제를 풀 때에는 (바로 생각나는 브루트포스 풀이 + 최적화할 수 있는 솔..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 회전할 부분 배열을 탐색하는 방법을 나눠서 2가지 버전으로 풀었다 한 가지 헤맸던 부분은 사방의 얼음 유무를 보고 얼음의 양을 감소시키는 로직에서 탐색 도중에 감소시키는 것이 아닌 탐색이 완료된 뒤 감소시켰어야 했는데 그 부분을 혼동하다 보니 정확한 값을 찾는 데 헤맸다 ㅠ #include #include #define pow2(x) (1= 0 && y < n; } void m..

https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 류호석배 알고리즘 코딩 테스트는 문제 퀄리티가 정말 좋아서 자주 푸는데 이번에도 새로운 코딩 테스트가 열렸다 실시간으로 참여할까 했지만 평일에 5시간이나 백준 문제를 풀면 너무 지칠 것 같아서ㅠ 천천히 풀어보려고 한다 이 문제는 특이하게 숫자 -> 숫자로 변환하는 과정에서 비트마스킹을 사용했다 아래의 그림처럼, 5를 3으로 바꾸기 위해서는 오른쪽 위의 LED를 켜고 왼쪽 위의 LED를 꺼야해서 2회의 반전이 필요하다 나는 각각의 위치에 대해 번호를 매기고 LED가 켜져있으면 1, 꺼..