본문 바로가기

BOJ29

그래프 (2) 문제들 2593 Elevator BFS DP N층짜리 건물에서 주어진 수열의 층에서만 멈추는 엘레베이터가 M대 있을 때 A층에서 B층까지 가기 위해 최소한으로 갈아타는 엘레베이터의 수 & 내렸던 층을 구한다. 트래킹때문에 좀 복잡했던 문제같음.. 더보기 현재 층 curf에서 탈 수 있는 엘레베이터 cure cure에서 내릴 수 있는 다음 층 nxtf nxtf가 B와 같다면 종료 다르다면 nxtf를 큐에 넣고 다음 엘레베이터 nxte로 갈아타며 dp를 업데이트 // Initiate for (int e : f[A]) dp[A][e] = { 1,0 }; Q.push(A); // BFS and Get Ans bool arrived_at_B = false; while (!Q.empty()) { arrived_at_B =.. 2021. 4. 26.
BOJ3716 도로 네트워크 3716번 도로 네트워크 1부터 N까지의 도시를 연결하는 N-1개의 도로가 주어지고 서로 다른 두 도시 D, E가 주어지면 D와 E를 연결하는 도로 중 가장 짧은 것의 길이와 긴 것의 길이를 구한다. 이때 모든 서로 다른 두 도시간 경로는 한 개만 존재한다. ⇒ 주어진 그래프가 트리이다. LCA문제임은 빠르게 파악할 수 있었다. 다만 공통조상뿐 아니라 공통조상까지의 도로의 길이 중 최댓값/최솟값도 알아야 했고 여기저기 헷갈린 탓인지 여러 차례 틀려서 힘들었다ㅠ 1. Get P 먼저 각 도시의 1, 2, 4, 8, ...번째 조상을 조사한다. 1을 root로 하여 BFS로 탐색하고, 조상을 탐색하며 도로 길이의 최소/최대를 구한다. P[ i ][ k ] r = 도시 i의 $2^{\mathrm{k}}$번째 .. 2021. 4. 23.
BOJ1086 박성원 1086 박성원 길이 50 이하의 자연수가 N(≤15)개 주어질 때 주어진 모든 자연수를 한 번씩 사용하여 이어 붙여 만든 자연수가 100이하의 자연수 K로 나누어 떨어질 확률을 구한다. example. (A) N=3 K=27 { 104, 4, 90 } 104490 104904 410490 490104 901044 904104 여섯 개 중 세 개만 나누어 떨어지므로 1/2 출력 (B) N=3 K=13 { 12, 2, 2 } 1222 1222 2122 2212 2122 2212 여섯 개 중 두 개만 나누어 떨어지므로 1/3 출력 * s[0]="12", s[1]="2", s[2]="2"일 때, s[0]+s[1]+s[2]="1222"와 s[0]+s[2]+s[1]="1222"를 모두 세야 한다. (순열 방식이 .. 2021. 4. 21.
KMP DP 트리 그래프 기하학 최근 푼 문제 1701 Cubeditor KMP idx(0~N-1)부터 N까지의 부분문자열에 대해 Pi를 구한다. idx에 대하여 최대 Pi값 - idx = 두 번 이상 나오는 가장 긴 부분문자열의 길이 * Pi를 구하는 시작점의 인덱스가 0이 아님에 주의해서 풀면 됨 16900 이름 정하기 KMP 주어진 문자열 S가 최소 K번 부분문자열로 등장하는 새로운 문자열 길이의 최솟값을 구한다. Pi를 구해 문자열 S에서 K-1번 반복해줄 부분 문자열을 구한다. 아래는 예시 S ada 3 pi 001 => (3-2)+2*3 S abc 2 pi 000 => (3-3)+3*2 S rr 5 pi 01 => (2-1)+1*5 S abcabcabca 3 pi 0001231234 => (10-3)+3*3 1509 팰린드롬 분할 DP 주.. 2021. 4. 16.
구현 (2) 지난 주 푼 문제 10253 헨리 구현 수학 써져있는 대로 구현하기만 하면 되는 문제. 5577 RBY팡! 구현 시뮬레이션 나 진짜 멍청했던게 RRRBRR 처럼 가운데에 하나 낀 애들만 색깔 바꿀 생각해서 계속 틀렸었다. 그래서 RRRBB있으면 하나도 팡! 안했었음 ㅋㅎㅋ RRRRBB로 바꿔서 팡 할 수 있는데,,, 한 이틀 뒤에 깨달았다.. 한 번 막힌 사고는 다시 흐르기가 참 어렵다.. 14601 샤워실 바닥 깔기 (Large) 분할정복 구현 처음에는 대칭성을 이용해 풀려고 했는데,,, 너무 복잡해졌고 ㄱ자 모양은 정사각형에서 한 칸 뺀 거라는 사실을 이용해서 생각해내야 했다. 사분할한 각 정사각형이 모두 비어있을 때만 꼭짓점을 채워 ㄱ을 만드는 형식을 반복하면 된다. 솔직히 너무 씽크빅이었지만 이런 것도 풀 줄 아는.. 2021. 4. 5.
BOJ13141 Ignition BOJ13141 Ignition 그래프가 주어지고, vertex 중 한 개에 불을 질렀을 때 그래프가 모두 타는 최소 시간을 출력 불은 1초에 1만큼 태울 수 있고 어디에 불을 붙여도 그래프가 반드시 전체 다 탈 수 있는 경우만 주어지며 시점과 종점이 같은 edge도 주어지고, 같은 시점과 같은 종점 사이 여러 개의 edge가 존재할 수 있다. 두 가지가 필요하다. 1. 한 vertex에 불이 도달할 수 있는 최소 시간 2. 두 vertex 간 edge가 모두 타는 시간 1의 경우 같은 vertex라도 불을 어디에 붙이느냐에 따라 값이 다르다. 결국엔 all vertex → all vertex의 최단거리를 구해야 하므로 floyd-warshall로 구한다. 2의 경우 두 vertex 간 가장 긴 edge.. 2021. 3. 17.
그래프 (1) 최근 푼 문제 아니,,블로그 정리를 어떻게 해야할지 모르겠다. 15559 내 선물을 받아줘 15886 내 선물을 받아줘2 2536 버스 갈아타기 5214 환승 15559 내 선물을 받아줘 → union find (Disjoint Set) 15886 내 선물을 받아줘2 → 문자열 내 EW의 개수 2536 버스 갈아타기 → BFS 가로/세로로 움직이는 버스를 나누어 갈아탈 수 있는 버스를 찾아내는 방법을 생각해낼 것 bfs 더보기 ver[N] ver[ i ] = x=i에서 세로로 움직이는 버스들 저장 hor[N] hor[ i ] = y=i에서 가로로 움직이는 버스들 저장 vis[N] vis[ i ] = i번째 버스를 타기까지 갈아탄 최소 횟수 int bfs() { // STEP 1. 시작점을 포함하는 버스 for (inf.. 2021. 3. 15.
기하학 (2) 계산 문제들 1207번 고층건물 - 기울기16190번 Rising Sun - 좌표, 기울기16115번 팬이에요 - 삼각함수1798번 원뿔좌표계상의 거리 - 좌표, 삼각함수1207번 고층 건물같은 간격으로 떨어져 있는 건물의 높이가 정수로 주어질 때각 건물의 옥상에서 보이는 다른 건물의 개수 중 최댓값 출력현재 건물과 보려고 하는 건물의 옥상을 이은 선분에 다른 건물이 교차하거나 만나면 안 된다. 즉, 현재 건물의 옥상을 점 A라 하고현재 건물에서 볼 수 있는 건물의 옥상을 왼쪽에서 오른쪽 순서로 각각 점 B1, B2, ...라 하면선분 AB1, AB2, ...의 기울기가 순서대로 증가해야 함 기울기가 같으면 안 됨. 8에서는 7만 보이고 6은 볼 수 없다. 높이가 극댓값인 건물만 보면 틀린다.낮은 건물에서 다른 건물.. 2021. 3. 15.
BOJ10714 케이크 자르기 2 10714번 케이크 자르기 2 자를 수 있는 케이크 조각의 크기가 주어질 때, JOI는 최선을 다해 케이크를 자르고, IOI는 양 끝 조각 중 무조건 큰 조각을 자른다. JOI가 얻을 수 있는 조각 합의 최댓값을 구해야 한다. 최선을 다하는 문제와 비슷하다. 다른 점은 JOI만 최선을 다한다 ⇒ dp배열에 두 명이 가진 케이크 양을 저장할 필요 없이 JOI가 얻게 된 조각 합의 양만 저장하면 된다. 케이크 조각은 직선형 배열이 아닌 원형 배열이다. 즉 시작과 끝이 정해져있지 않다 ⇒ i, j의 대소에 관계없이 전체 dp 배열을 채워야 한다. 가령 N=5일 때 dp[ 2 ][ 4 ]는 2, 3, 4번째 조각이 남아있을 때 dp[ 4 ][ 2 ]는 4, 5, 1, 2번째 조각이 남아있을 때 JOI가 얻은 케.. 2021. 1. 30.
BOJ2342 Dance Dance Revolution 2342번 DDR 뭔가 경찰차랑 비슷한 느낌의 DP 눌러야하는 DDR의 발판 번호가 주어지면 발판을 순서대로 누르기 위한 최소의 힘을 구해야 한다. a[ i ][ j ]=이번 발판까지 고려하여 오른발이 i, 왼발이 j를 누를 때 사용한 최소의 힘 STEP 1. 발의 움직임에 따라 사용하는 힘을 배열에 저장 사차원 배열을 이용했다. p[ a ][ b ][ c ][ d ]=오른발 a, 왼발 b에서 오른발 c, 왼발 d 가 될 때 사용하는 힘 //same posit: 1i,j -> i,j i=0-4 j=0-4 //0->1/2/3/4: 2i,0 -> i,j i=0-4 j=1-4 //moving adj: 3i,j -> i,j+1 //moving opp: 4 //STEP 1. Set Power p int p[5][.. 2021. 1. 30.

티스토리툴바