문제 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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYVgWGZKOroDFAQK SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 예상 만약 지금 내가 K개의 함선을 가지고 있다면, 행성 인구가 K보다 작거나 같은 행성에 침략을 할 수 있는데 침략할 수 있는 행성 중 가장 인구가 많은 행성에 침략과 동원을 해야한다. => 제일 많이 함선을 늘릴 수 있는 방법 위 방법으로 풀기 위해 처음에는 그냥 배열에 인구 수를 넣고 정렬한 뒤, 뒤에서부터 탐색하면서 풀었다. 근데 N의 개수가 20만이라서 최악이 20만 x 20만 ..
문제 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://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AXmwOSJaSNIDFARX&categoryId=AXmwOSJaSNIDFARX&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=4 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 예상 타일이 무조건 2x2 이기 때문에 탐색을 하면서 만나는 부서진 타일을 정사각형의 왼쪽 위를 기준으로 두고,..
