baekjoon 2206 벽 부수고 이동하기 2206번 벽 부수고 이동하기 접근 a~>b~>c 이런 경로가 있다고 하자. 일반적인 bfs의 경우 k길이 search를 끝내고 k+1 search를 시작하니까 a에서b에 처음 도착만 하면 그게 최단 길이다. k-1까지는 도착 못했다는 거니까 이번 문제에서는 최대 한번 까지 벽을 뚫을 수 있다...

baekjoon 1149 RGB거리 1149번 RGB거리 접근 대놓고 dp였다. dp(i, k): i번째가 k로 색칠했을 때 최소 (k = 0, 1, 2) dp(i, k) = price(i, k) + min(dp(i+1, (k+1)%3 ), dp(i+1, (k+2)%3)) 코드 #include <iostream> #include &l...

baekjoon 1043 거짓말 1043번 거짓말 접근 이 문제를 잘 이해하는 것이 중요하다. 이 문제는 사람들을 두 그룹으로 나누는 것이 핵심이다. 과장할 사람들과 진실을 말할 사람들로 나눠야한다. 즉, 한 사람에게는 진실 혹은 과장 하나만 말해야한다. 둘을 다 말하면 무조건 거짓이 들키는 조건이다. 과장을 먼저 말하고 진실을 말한다고 거짓이 들...

baekjoon 1697 숨바꼭질 1697번 숨바꼭질 접근 DLRS문제 풀었을 때와 같은 방식으로 하면 될 것 같다. visited사용해서 최초만 기록해서 중복하지 않도록하고 pair로 지금 몇초 지나서 만들어 진건지 기록한다. 코드 #include <iostream> #include <vector> using names...

baekjoon 2178 미로탐색 2178번 미로탐색 접근 정해진 위치에서 최단거리 탐색이니까 bfs이다. 코드 #include <iostream> //iostream이 string 포함해서 string 헤더 따로 필요 없더라 #include <vector> #include <queue> using namesp...

baekjoon 2667 단지번호붙이기 2667번 단지번호 붙이기 접근 저번에 만들었던 dfsall 변형시키면 될 것 같다. 코드 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace st...

baekjoon 5525 IOIOI 5525번 IOIOI 접근 서브태스크가 있는 걸로 봐서 최적의 알고리즘을 만들지 않으면 100점 통과하지 못하지 않을까 싶었다. S에 있는 원소들을 여러번 확인하는 것은 비효율이 발생한다. 최소로 생각해보면 딱 한번씩만 확인해서 O(M)에 끝내는게 바람직한다. 만약 길이 2n+1을 확인했는데 맞다면, 그다음 2...

baekjoon 6064 카잉 달력 6064번 카잉 달력 접근 몇 가지 예시들을 보자마자 나머지로 접근해야 겠다는 생각이 들었다. 결과적으로 m으로 나눈 나머지가 x, n으로 나눈 나머지가 y인 것이다. 그런데 조금 달랐던 것은 m, n의 숫가까지 포함이고 오히려 나머지 0이 없으니까 예외처리를 좀 해줘야한다. 코드 #include <io...

baekjoon 11286 절댓값 힙 11286번 절댓값 힙 접근 우선순위 큐 사용해서 하면 될 것 같다. 저번 vector만들 때 썼던 방식처럼 연산자 오버로딩 방식으로 하면 될 것 같다. 코드 #include <iostream> #include <queue> using namespace std; struct Comp...

baekjoon 11403 경로 찾기 11403번 경로 찾기 접근 각 node에서 dfs 돌리면 될거라고 생각했다. 그런데 이제 기본 dfs와 다르게 처음 자기가 시작하는 node에서는 visited라 표시하면 안되니까 좀 변형시켰다. 코드 #include <iostream> #include <vector> using n...