0. 문제 9658번: 돌 게임 4 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. 문제 이해 2개의 돌을 뺄 수 없다는 조건 때문에 수학적 규칙을 찾기 어려웠다. N=1000이고 제한시간은 1초다. 1초를 1억으로 가정하면 시간복잡도는 O(n^2)쯤이다. 모든 경우의 수를 다 구해서 풀면 O(n^3)이다. DP로 풀어야 한다. 상근이가 이기는지 지는지 알아내는 방법은 다음과 같다. 돌의 개수가 1 ~ 5까지는 비교적 쉽게 구할 수 있다. 돌의 개수가 6일 때는 6에서 1, 3, 4개를 빼본다. 6 - 1 = 5, 6 - 3 = 3 그리고 6 - 4 = 2에서 단 한 번이라도 상근이가 이기면 6에서도 상근이가 이긴다. (= 모든 경우에서 창영이가..

1. 입력 입력 속도 비교 여러가지 언어와 입력 방법을 이용해서 시간이 얼마나 걸리는지 비교해 보았습니다. 방법: 첫째 줄에 정수의 개수 N (= 10,000,000), 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일 www.acmicpc.net 가. Scanner import java.util.Scanner; public class Test1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); String[] foods = new String[num]; for(int i=0; i

0. 문제  SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 1. 문제 이해 최장 증가 부분 수열에 관한 문제이다. 별다른 접근 방법이 생각나지 않기 때문에 모든 경우의 수를 실행하고 그 결괏값을 비교하기로 했다. a1, a2, a3, a4, a5, …, an 수열이 주어진다면 수열의 크기는 n이다. 수열에서 파생될 수 있는 순서가 바뀌지 않는 모든 부분 순열은 수는 2^n이다. 2. 시간 초과import java.io.*;import java.util.StringTokenizer;class Solution { static int n; static int ret; public static void ..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 메모리 bit 중 하나를 골라 0인지 1인지 결정하면 해당 값이 메모리의 끝까지 덮어씌우는 것이다. 예를 들어 지금 메모리 값이 0100이고, 3번째 bit를 골라 1로 설정하면 0111이 된다. 원래 상태가 주어질 때 초기화 상태 (모든 bit가 0) 에서 원래 상태로 돌아가는데 최소 몇 번이나 고쳐야 하는지 계산해 보자. 1. C++ #include #include #include using namespace std; int solve(vector& input){ int cnt = 0; char before = '0'; for(int i = 0; i..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 민기가 좋아하는 햄버거를 먹으면서도 다이어트에 성공할 수 있도록 정해진 칼로리 이하의 조합 중에서 민기가 가장 선호하는 햄버거를 조합해주는 프로그램을 만들어보자. 1. C++ 가. 제출 #include #include using namespace std; const int MAXN = 20; int n, l, ret; int t[MAXN], k[MAXN]; void solve(int depth, int cal, int score){ if(depth == n){ if(cal ret){ ret = score; } return; } if(cal > l) re..

0. 문제 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 1. 제출 #include #include #include using namespace std; int n, l; vector find(){ vector vec; int cur = l; while(cur > n >> l; vector vec = find(); for(int i : vec) cout N >> L; for (int length = L; length = 0) { // 등차수열의 시작 값 계산 int a1 = (N - constant) / length; // 길이가 100보다 작거나..

0. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 문제 이해 이건 인접리스트를 만들고 dfs로 connected component의 수를 세는 문제라고 생각했다. 2. 실패 가. 실패 : 입력값 범위 #include #include #include using namespace std; const int MAX_N = 100; int n, m, visited[MAX_N]; vector adj[MAX_N]; void dfs(int node){ visited[node]++; for(int next : adj[node]){ if(visited[next]) continue; dfs(next); } retu..

1. 파리퇴치3 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 가. 제출 #include #include using namespace std; int n, m; int a[15][15]; int dy[2][4] = {{1, -1, -1, 1}, {1, 0, -1, 0}}; int dx[2][4] = {{1, 1, -1, -1}, {0, 1, 0, -1}}; int sum(int y, int x){ int sum[2]; for(int i = 0; i = n); if(underflow || overflow) continue; sum[i] += a[ny][nx]; } } } return max(sum[0], sum..