문제 링크 2502번: 떡 먹는 호랑이 풀이 먼저 첫째날에 x개, 둘째날에 y개 줬다고 했을 때 d째 날에 x와 y를 이용한 연립방정식을 구한다. 이건 DP로 풀면 된다. x와 y는 따로 계산 될 것이니 각 {0, 1, 0, }, {0, 0, 1, }로 초기화해서 전전날과 전날의 합을 구하면 된다. 예를 들어, 여섯 번째 날에 x와 y의 연립방정식을 구하고 싶다면, x[6]에 있는 3, y[6]에 있는 5를 이용해 3x+5y라는 식을 만들 수 있다. 식을 구했으니 이젠 완전 탐색을 이용해 x와 y를 구하면 된다. 단, 여기서 y는 x보다 크거나 같아야 하므로 내부의 반복문은 i부터 시작하도록 한다. x[d]*i+y[d]*j가 k와 같다면 출력하고 return한다. 코드 #include using name..
문제 링크 15686번: 치킨 배달 풀이 조합으로 푼 문제 먼저 값을 입력 받으며 치킨집의 좌표와 집의 좌표를 각각 chicken과 house 벡터에 넣는다. func 함수를 통해 치킨집의 조합을 찾아 최소가 되는 도시의 치킨 거리를 찾는다. 현재 인덱스인 curIdx부터 chicken.size()-1까지 반복문을 돌며 조합을 만든다. chickenList에는 현재 조합에 들어있는 치킨집의 좌표들이 들어있다. 왜 반복문이 curIdx부터 실행하냐면, 이전 인덱스 것들은 이전 func함수에서 실행했을 것이므로! 순열이 아닌 조합이기 때문에 (1,2)든, (2,1)이든 같다. i 인덱스의 치킨집을 조합에 넣었다면, 그 다음 인덱스들을 체크해서 넣어줘야 한다. 그렇게 만든 치킨집의 조합 사이즈가 m이 됐다면,..
문제 링크 2573번: 빙산 풀이 DFS 문제 while 반복문으로 한 해의 빙산 덩어리 개수를 계산한다. 매 년마다 DFS로 덩어리의 개수를 세야하기 때문에 visit은 지역변수로 넣어줬다. cnt는 덩어리의 개수이고, flag는 빙산이 다 녹았는지 체크하기 위한 bool 변수이다. 만약 방문하지 않은 빙산이 있다면 덩어리 개수를 +1해주고, DFS를 실행한다. 빙산이 있다는 뜻이므로 flag도 false해준다. DFS 함수는 덩어리 하나를 체크하기 위한 함수임과 동시에 일 년이 지나고 빙산을 만들어준다. 덩어리 개수 체크를 위해 visit은 받아와주었고, 방문처리를 한다. zeroCnt에는 해당 빙산이 바다와 맞닿아있는 면적(상하좌우)이 구해질 것이다. 해당 빙산의 상하좌우를 체크해 범위 밖이거나 방..
문제 링크 16236번: 아기 상어 풀이 별로 안 어려운 것 같았지만 장장 4시간이나 걸려서 푼 문제... BFS 문제.. 우선 순위도 잘 파악해야 한다. 처음엔 BFS 한 번 돌려서 풀려고 했지만 한 번 먹을 때마다 상어의 위치를 초기화 해주어야 하고, 거리 > 행 > 열 순으로 물고기를 먹어야 한다.... 처음 입력받을 때 아기 상어의 위치가 들어오면 위치를 저장하고 0으로 넣어준다. 나중에 못가는 상황이 생길 수 있음 먹을 수 있는 물고기가 없을 때까지 BFS를 돌린다. 한 번 돌릴 때마다 canEat에 먹을 수 있는 물고기들이 쌓일 것임 BFS함수부터 설명하자면, 먼저 상어가 움직일 때마다 시간(나는 거리라고 했다)을 저장하기 위해 dist를 -1로 초기화한다. 여느 BFS 문제와 같이 queue..
문제 링크 1759번: 암호 만들기 풀이 백트래킹 문제 알파벳을 입력받으며 모음인지, 자음인지 체크하여 pair로 넣는다. (모음은 1, 자음은 0) 알파벳을 오름차순 정렬한 뒤, DFS 시작 인자를 설명하자면 curIdx는 alpha에서 현재 인덱스, curString은 현재까지 만든 문자열, cnt는 모음의 개수이다. 만약 현재 문자열의 길이가 l과 같고, 모음이 1개 이상이고 자음이고 2개 이상이면 curString을 출력한다. alpha의 현재 인덱스 curIdx부터 시작해서 문자열(curString)을 만든다. DFS함수 재귀 호출을 통해 다음 인덱스의 문자를 더해 문자열을 만든다. 코드 #include #include #include #include using namespace std; voi..
문제 링크 2583번: 영역 구하기 풀이 영역의 개수와 넓이를 구하는 BFS문제 먼저 원점이 왼쪽 밑이고, 입력받는 x와 y의 값이 칸 기준이 아니기 때문에 바꿔줘야할 필요가 있다. x1과 x2는 왼쪽에서부터이므로 사각형의 x범위는 x1~x2-1이 된다. y1과 y2는 밑에서부터이므로 사각형의 y범위는 m-1-(y2-1)~m-1-y1이 된다. 그렇게 입력 받은 범위를 1로 채우고 처음부터 모눈종이를 돌면서 0인 부분부터 탐색을 시작한다. 영역의 개수를 구해줘야하므로 cnt++ 해준다. BFS 함수로 탐색을 하는데, queue를 이용한다. visit 배열 없이 바로 board에 체크해준다. 영역 넓이를 구해야하므로 지역 변수 cnt를 0으로 초기화 한뒤, queue가 비어서 더이상 나아갈 수 없을 때까지 ..
문제 링크 10986번: 나머지 합 풀이 누적합 문제인데, 모듈러 연산도 곁들인 .. 참고로 합 모듈러 연산은 (a+b)%m = ((a%m)+(b%m))%m이다. 합이 M으로 나누어 떨어지는 구간을 구하면 되므로, 누적합의 모듈러를 구하는 것. 이 것은 위에 설명한 합 모듈러 연산으로 바꾸어 생각하면 된다. 값을 입력 받으면서 누적합의 모듈러를 구한다. 그렇게 나온 값의 총 개수를 구하기 위해 cnt 벡터에 넣어준다. 각 결과값의 개수가 구해질 것이다.(cnt) 누적합의 모듈러 값이 0인 것은 해당하는 인덱스까지 누적합이 m으로 나누어 떨어진다는 것이고, 다른 두 개의 인덱스가 같은 모듈러 값을 가지면, 해당 인덱스부터 인덱스까지의 누적합이 m으로 나누어 떨어진다는 것이다. 그래서 개수를 구한 것이고, ..
문제 링크 1707번: 이분 그래프 풀이 이분 그래프란 두 집합이 있을 때 하나의 정점은 하나의 집합에 속해야 하는데, 인접한 정점은 같은 집합에 포함되면 안된다는 그래프이다. 주의할 점은 시작 정점에서 연결되지 않은 정점도 체크를 해줘야한다는 것. 테스트 케이스의 수만큼 입력을 받고, 각 테스트 케이스마다 인접 리스트를 초기화해준다. 무방향 그래프이기 때문에 입력 받은 두 정점을 양쪽에 다 넣어줘야한다. BFS를 시작할텐데 정점을 돌며 visit이 0인 (방문하지 않은 정점)일 경우 BFS를 시작해준다. 연결되지 않은 정점 체크를 위함이다. 다른 BFS문제와 같이 queue를 이용하는데, 현재 정점을 q에 넣고, visit도 집합 1로 설정해주며 q가 빌 때까지 반복한다. 다음 정점의 visit이 0이..
문제 링크 16928번: 뱀과 사다리 게임 풀이 BFS 문제 뱀과 사다리 입력을 받으며 인접리스트 adj를 초기화해준다. BFS를 시작한다. 주사위 횟수가 담기는 dist 배열을 INF로 초기화해준다. 이 때 INF는 주사위를 1로 돌려 100칸까지 가는 경우가 최대이기 때문에 101로 정의했다. 첫번째 칸부터 시작해서 queue가 빌 때까지 반복한다. adj[cur].size()가 0보다 큰 경우는 뱀이나 사다리를 타야하고, 아닌 경우는 주사위를 돌려야하기 때문에 경우를 나누어준다. 뱀이나 사다리가 있다면 인접 리스트를 확인해 다음 칸의 dist가 현재 칸의 dist보다 클 경우, 다음 칸을 작은 값으로 갱신해준 뒤 q에 넣어준다. 주사위를 돌릴 경우 1~6까지 주사위를 돌릴 수 있으므로 dist[ne..
문제 링크 11401번: 이항 계수 3 풀이 이항 계수의 식과, 페르마의 소정리, 모듈러 연산을 알아야 풀 수 있는 문제 보통 이항 계수 문제는 DP나 재귀로 풀 수 있는데 입력값이 너무 크기 때문에 시간 초과가 난다. 이런 경우 공식을 이용해 풀어야한다. 우리가 구해야 할 것은 이항 계수를 1000000007 (이하 mod)로 나눈 값이다. 해당 값을 바로 구할 수 있다면 좋겠지만 분수의 나머지 구하기는 힘들기 때문에 페르마의 소정리를 이용해야 한다. 페르마의 소정리란 p가 소수일 때, a^p를 p로 나눈 나머지가 a를 p로 나눈 나머지와 같다는 정리이다. 해당 식을 변형해서 맨 마지막 식까지 만들 수 있고 저 식을 우리가 구해야 하는 값의 공식에 적용할 것이다. 이항계수의 분자를 A, 분모를 B, 나..
