본문 바로가기

알고리즘78

14238번 - 출근기록(dp, dfs) 문제:A는 매일 매일 출근할 수 있다. B는 출근한 다음날은 반드시 쉬어야 한다. C는 출근한 다음날과 다다음날을 반드시 쉬어야 한다. 따라서, 모든 출근 기록이 올바른 것은 아니다. 예를 들어, B는 출근한 다음날 쉬어야 하기 때문에, "BB"는 절대로 나올 수 없는 출근 기록이다. 출근 기록 S가 주어졌을 때, S의 모든 순열 중에서 올바른 출근 기록인 것 아무거나 출력하는 프로그램을 작성하시오.첫째 줄에 출근 기록 S가 주어진다. S의 길이는 50을 넘지 않는다.S의 모든 순열 중에서 올바른 출근 기록인 것을 하나만 출력한다. 만약, 올바른 출근 기록이 없는 경우에는 -1을 출력한다. 풀이:올바른 출근기록 하나만 출력해야 하며, 각 출근 기록의 길이는 동일하다.즉, 올바른 순열이며, 출근 기록의 길.. 2024. 9. 3.
12996번 - Acka(재귀, dp) 문제: 풀이:일반적인 재귀로 풀기에는 너무 많은 반복이 발생한다.S의 범위가 크지 않은 것으로 보아 dp를 이용해 풀면 좋을 것 같다.그렇다면 어떻게 dp를 이용해야 할까? 아래 예시를 통해 알아보도록 하자. 입력: 3 2 1 1각 차례에서 노래를 선택할 수 있는 방법은 아래와 같다. 인원 1인원 2인원 31OOO2OOX3OXO4XOO5OXX6XOX7XXO총 7가지 방법을 선택할 수 있다. 주어진 입력에서 어떤 경우의 수로 앨범을 만들 수 있나 살펴보자. 일단 방식 1을 첫번째로 택해봤다.S인원1인원2인원33211210010000XXX방식1을 택하면 앨범이 만들어지지 않는다.계속해서 2번째 방식을 택해보겠다.S인원1인원2인원3인원1인원2인원3인원1인원2인원332112112112101101101100000.. 2024. 8. 31.
11049번 - 행렬곱셈순서(dp) 문제: 풀이:행렬곱셈부터 소개하자면 5x3 행렬과 3x2 행렬이 곱해지려면 5x3x2의 연산이 필요하며, 그 결과 5x2행렬이 만들어진다.같은 원리로 3x2행렬과 2x6 행렬이 곱해지려면 3x2x6의 연산이 필요하며, 그 결과 3x6행렬이 만들어진다. (5 3) (3 2) (2 6) (6 1) (1 4)의 행렬이 주어졌다고 예시를 들고 그 연산과 결과에 대해 설명하겠다.바로 옆에 붙은 행렬끼리의 연산 횟수부터 구해보겠다.행렬이 2개일때 최소 연산 횟수5 33 22 66 11 4연산 횟수5 x 3 x 23 x 2 x 62 x 6 x 16 x 1 x 4만들어진 행렬5 23 62 16 4기본적인 행렬 곱셈 방법의 결과 연산 횟수와 새로운 행렬이 나왔다. 이제 위 행렬을 이용해보자행렬이 3개일때 최소 연산 횟수.. 2024. 8. 29.
12869번 - 뮤탈리스크(bfs) 문제: 풀이:scv의 체력이 주어져 있고, 뮤탈의 공격 방식도 정해져있다.그렇다면, 모든 scv의 체력이 다 닳을때까지 뮤탈이 여러 방식으로 공격해보면 될 것이다.자, 가능한 모든 경우의 수로 한대씩 때려보자.위와 같은 결과가 나올 것이다.만약 그 다음에도 한번씩 때려보면 6 x 6의 경우의 수가 나올 것이고, scv가 모두 죽는 경우의 수에 도달할 것이다.위 그림을 보면, bfs를 사용하고 있다는 것을 알아볼 수 있을 것이다.중복이 일어나지 않도록 visited 배열을 만들어 코드를 작성하면 쉽게 풀 수 있을 것이다. 뮤탈의 공격 순번을 미리 저장해 놓는다.bfs를 위한 visited 배열은 3차원 배열로 저장해 놓을 것이다.int[][] attack = {{9, 3, 1}, {9, 1, 3}, .. 2024. 8. 27.

티스토리툴바