문제 https://www.acmicpc.net/problem/27958 27958번: 사격 연습 N×N 크기의 보드 판이 존재하며, 1개 이상의 표적이 존재한다. 한 학생은 사격을 연습하고 있으며, 1번부터 K번까지 K개의 총알을 가지고 있다. 학생은 총 K번의 사격을 진행하며, 1번부터 K번까지 www.acmicpc.net 풀이 예상 시뮬레이션. . 풀이방법 (접근 방법 & 시간복잡도) N과 K의 범위가 작기 때문에 모든 경우를 탐색하는 시뮬레이션 문제이다. dfs로 타고 들어가기 때문에 보드를 잘 리셋해줘야 한다. 그렇기 때문에 dfs 들어가자마자 가지고있던 배열을 복사해서 사용하고 복사한 배열을 다음 총알쏘는 부분으로 넘겨주었다. 표적을 만났을 때, 로직순서는 10이상의 표적이라면 => 보너스 점..
문제 https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 예상 시뮬레이션 문제 풀이방법 (접근 방법 & 시간복잡도) 먼저 이동 부분은 왼, 아, 오, 위 순으로 왼 아 오오 위위 왼왼왼 아아아 오오오오 위위위위 왼왼왼왼왼 ... 이런 방식으로 진행 되기 때문에 왼쪽과 오른쪽일때 한번씩 더 간다는 점을 이용했다. int direction = 0; //왼아오위 int keep = 0; //토네이도 순서 왼, 아, ..
문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 예상 1. dp[] 배열을 활용한다. dp[i] = i번째 에서 가장 긴 증가하는 부분 수열의 개수 2. 현재 숫자에서 이전 숫자들을 보면서 dp[i]를 갱신한다. ex) input 6 10 20 10 30 20 50 nums[] = {10, 20, 10, 30, 20, 50} dp[] = {0, 0, 0..
문제 https://www.acmicpc.net/problem/2040 2040번: 수 게임 순서대로 나열된 n개의 수를 두고, A와 B 두 사람이 번갈아가며 진행하는 게임이 있다. 편의상 나열된 수를 순서대로 a1, a2, ..., an이라고 하자. 게임은 A부터 시작하는데, A는 an을 포함하여 연속된, www.acmicpc.net 풀이 예상 현재 위치에서 (내가 먹을 수 있는 값) - (그 다음 턴에서 상대가 최소로 먹을 수 있는 값) 이 최소일 때를 찾아야 한다. answer가 음수라면 A가 먹은 값보다 B가 먹은 값이 더 큰 것 이므로 A가 이긴다. 예를 들어서 nums[] = {10, 7, 2} 라면 1) A 가 2를 선택하면, B는 7을 선택한다. => B가 7을 선택하면 A가 10을 선택한..
문제 https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 풀이 예상 이전 돌멩이의 개수를 보고 승리를 예측 하는 것 이라고 생각했고 돌을 1, 3, 4 개씩 가져갈 수 있기 때문에 지금 돌멩이의 개수에서 -1, -3, -4 부분을 보고 현재 돌멩이에서 누가 이기는지 예측하는 것 이라고 생각했다. 돌을 딱 맞춰가지 않아도 되는 줄 알고,, 헛다리 짚었었는데 ex) 2 라면 상근이가 3개나 4개 선택해서 가져가면 이기는줄.. 돌 개수를 딱 맞춰가야 했었다. N을 늘려가면서 누가 이기는지 표로 그려 봤을 때, 다음과 같은 규칙을 찾을 수 있었다. i-1, i-3, i-4..
문제 https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 풀이 예상 dp배열의 의미는 dp[날짜][지각횟수][연속된결석횟수] 이다. 첫날부터 출석, 지각, 결석 인 경우를 체크하면서 dfs를 진행한다. 지각이 2번인경우 또는 결석이 연속으로 3번인 경우는 0을 리턴한다. 날짜가 N이 되었다면 1을 리턴한다. dp배열을 처음에 전부 -1으로 초기화 해 두고 -1이 들어있다면 dfs로 찾고, -1이 아닌 값이 있다면 한번더 찾지말고 바로 그 값을 쓴다.(메모이제이..
문제 https://www.acmicpc.net/problem/14677 14677번: 병약한 윤호 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 약을 먹어야 하는 날짜인 N이 주어진다. (1 ≤ N ≤ 500) 두 번째 줄에는 3N개의 약의 상태가 주어지는데, 아침 약은 B, 점심 약은 L, 저녁 www.acmicpc.net 풀이 예상 dp 배열로 start, end 지점에서 방문한 적이 있다면 메모를 해 두고, 또 방문 했을 때 바로 꺼내서 쓸 수 있도록 했다. 메모를 하지않으니까 시간초과가 났고, 메모를 하니까 통과할 수 있었다. 풀이방법 (접근 방법 & 시간복잡도) B:0, L:1, D:2 로 저장 해 두고, 시작점과 끝점, 먹어야할 것을 들고 다니면서 갱신해준다. 지금 먹어야 할 약..
문제 https://www.acmicpc.net/problem/17351 17351번: 3루수는 몰라 주어진 규칙을 따라 이동하면서 부분 문자열로 "MOLA"를 최대한 많이 포함하는 S를 만들고, 이때 S에 포함된 부분 문자열 "MOLA"의 개수를 출력한다. www.acmicpc.net 풀이 예상 알파벳 순서대로 M, O, L, A 를 1, 2, 3, 4 로 두고 점점 증가시킨다. MOLA가 하나 완성되었다면 다음 M, O, L, A의 값은 5, 6, 7, 8 이다. 이 것을 반복하다보면 M을 나머지연산하면 1, O를 나머지연산하면 2, L를 나머지연산하면 3, A를 나머지연산하면 4 가 된다. 이러한 방법을 이용해서 dp배열을 갱신한다. 이동할 때, 오른쪽방향과 아래방향으로밖에 못움직이기 때문에 현재 ..
