코딩하기 좋은날

https://www.acmicpc.net/problem/3184 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 n가지 종류의 동전으로 k원을 만들 수 있는 경우를 구하는 문제입니다. dp를 이용하여 가장 금액이 작은 동전으로 만들 수 있는 경우들을 각각 저장하며 문제를 해결하여야 합니다. 예를들어 문제의 예시인 1 2 5 원짜리 동전이 있고 10원을 만드는 가지를 구하려면 1원으로 1~10원을 만드는 경우를 모두 갱신하고 그다음 2원을 사용하여 갱신하는 경우를 더해주며 5원까지 가면 각각 금액을 만드는 모든 경우를 생각 할 수 있습니다. 따라서 dp[k] = dp[k] + dp[k-coin[i]] 라는 점화식이 나오게 됩니다. 식의 의미는 k원을 만드는데 i번째 동전을 사용하는 경우 (..

https://www.acmicpc.net/problem/1010 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 강의 서쪽에 N개의 다리가 있고 강의 동쪽에 M개의 다리가 있을 때 연결 할 수 있는 경우의 수를 출력해야 합니다. 테스트 케이스가 여러가지이므로 한번에 답을 다 구해놓고 그에 맞게 출력하도록 해야 하는데 M개중에 N개를 선택하는 조합으로 볼 수 있습니다. 즉 mCn으로 볼 수 있고 이는 mCn = m-1Cn-1 + m-1Cn 으로 나타낼 수 있습니다. 따라서 이에따라 모든 최대 경우까지 값을 모두 구하면 됩니다. 다음은 코드입니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); ..

https://www.acmicpc.net/problem/2193 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 N자리의 이친수를 구하는 문제입니다. 이친수란 0으로 시작하지 않고 1이 연속해서 나오지 않는 숫자를 뜻합니다. 먼저 1자리의 경우를 보면 1 한가지만 가능합니다. 2자리인 경우도 10 으로 한가지만 가능합니다. 3자리인 경우는 101, 100 으로 두가지경우가 가능합니다. 4자리의 경우 1010, 1001, 1000 으로 세가지 경우가 가능합니다. 5자리의 경우를 보면 10100, 10101, 10010, 10001, 10000 총 5가지 경우가 가능합니다. 여기서 이제 규칙을 찾아보면 n자리의 경우 n-1자리의 모든경우에 0을 덧붙이는 경우는 가능합니다. 그렇다면 1을 덧붙..

https://www.acmicpc.net/problem/3184 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 마당에 양과 늑대가 있는데 양이 더많다면 양이 늑대를 모두 해치우고 그렇지 않다면 늑대가 모두 양을 해치울때 최종적으로 남는 양과 늑대의 수를 출력하는 문제입니다. 우선 마당이 형성되기 위해서는 사방이 울타리로 둘러 쌓여 있어야 하므로 저는 dfs를 통해 하나의 마당영역을 탐색하며 늑대와 양의 수를 찾아 내었습니다. dfs가 끝난뒤 조건에따라 양이 많으면 양을 +해주고 그렇지 않으면 늑대를 + 해준뒤 또다른 영역이 있는지 탐색하는식으로 모든 영역을 탐색하는 방법으로 문제를 해결하였습니다. 다음은 코드입니다. #include #include using namespace std; ..

https://www.acmicpc.net/problem/9205 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 집의 좌표와 n개의 편의점의 좌표와 도착지점의 좌표를 입력받고 이동거리 50m당 맥주한병을 마셔야 하는데 총 보유할 수 있는 맥주는 20병이므로 다음 편의점까지의 거리가 1000m이내에 있다면 계속해서 이동하며 도착지점까지 맥주를 마시면서 갈 수 있는지 여부를 확인하는 문제입니다. 좌표사이의 거리는 맨해튼거리인 x좌표의 차이 + y좌표의 차이라고 되어있으므로 그렇게 계산해 주시면 됩니다. 저는 bfs를 통해 q의 front에 저장되어 있는 지점과의 차이가 1000m이내에 있는 지점이 있다면 q에 push를 해 주었습니다. 그리고 q의 front에 있는 좌표에서 도착지점까지의 거..

https://www.acmicpc.net/problem/4179 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 지훈이가 불을 피해 미로를 탈출할 수 있는 가장 빠른 시간을 출력하는 문제입니다. 이 문제는 지훈이도 이동을 하지만 불또한 상하좌우로 벽이 없는곳은 확산이 되므로 bfs를 통해서 불과 지훈이 모두를 이동시켜 주어야합니다. 벽이 있는 부분은 visited배열에 방문 불가능으로 설정해놓고 먼저 불을 확산시킵니다. 그이후 지훈이가 이동을 하는데 지훈이가 방문한 지점은 2로 설정합니다. 그 이유는 지훈이가 방문한 길은 지훈이는 재방문이 불가능하지만 불은 방문이 가능하기 때문입니다. 따라서 지훈이는 visited가 1,2인 지점이 방문 불가능하고 불은 visited가 1인지점만 방문이 ..

https://www.acmicpc.net/problem/1874 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 수열을 입력받고 이러한 수열을 스택을 이용해서 나타낼 수 있다면 push와 pop을 어떻게 진행해야 하는지 출력하고 그럴 수 없다면 NO를 출력하는 문제입니다. 이때 스택에 push는 반드시 1부터 n까지 순서대로만 들어 갈 수 있습니다. 따라서 저는 pushnum이라는 변수를 선언해 어떤 숫자까지 push가 되었는지 체크를 하였습니다. 처음에는 우선 수열의 맨처음 숫자만큼 스택에 push가 됩니다. 저는 +/-기호는 벡터에다가 저장해 두었습니다. 맨처음 숫자만큼 push를 하고 push를 마치고 나면 첫번째 숫자는 나와야 하므로 pop을 해줍니다. 그리고 두번째 수열의 숫자부..

https://www.acmicpc.net/problem/11403 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 정점 N개를 가지는 그래프의 인접 행렬을 입력 받고 정점 i에서 j로 갈 수 있는 경우가 있다면 1 그렇지 않다면 0으로 나타나는 행렬을 출력해야 합니다. 저는 이 문제를 bfs를 통해서 풀었습니다. i에서 j로 갈수 있는경우가 있는 경우 bfs 함수로 들어가서 visited[i][j] 를 1로 만들어주고 그후 j에서 다른 위치로 갈 수 있는지를 확인후 예를들어 j 에서 k로 갈 수 있다면 i -> j -> k 의 경로를 통해 i에서 k로 갈 수 있으므로 visited[i][k]를 1로 만들어 주는 식으로 i에서 어떤 다른 경로를 거쳐서 어떠한 경로로 갈 수 있는 모든 경우를..