반응형 PS 문제 풀이/SWEA75 [SWEA] 1284 수도 요금 경쟁 출처: SWEA Input 2 9 100 20 3 10 8 300 100 10 250 Output #1 90 #2 1800 A, B 요금 측정에 대한 식을 세워 간단히 해결 할 수 있습니다. #include using namespace std; int solve (int P, int Q, int R, int S, int W) { int A, B; // A 요금 A = P * W; // B 요금 (R 리터보다 많이 사용했는지 확인) if (W > R) B = Q + S * (W - R); else B = Q; // A, B 중 더 작은 값을 반환 return A > testCase; for (int tc = 1; tc > .. 2021. 3. 1. [SWEA] 1234 비밀번호 출처: SWEA Input 10 1238099084 16 4100112380990844 Output #1 1234 #2 4123 스택(Stack) 사용. 입력받은 문자를 stack에 한개씩 push 합니다. 같은 문자가 top에 위치한 경우에는 push하지 않고 top에 있는 것을 pop 합니다. #include #include #include using namespace std; int main() { int testCase = 10; stack stack, answer; int len; string str; for (int tc = 1; tc > len >> str; for (int i = 0; i < len; i++) { if (!stack.empty() && stack.top() == str[i].. 2021. 3. 1. [SWEA] 3376 파도반 수열 출처: SWEA Input 2 6 12 Output #1 3 #2 16 #include #include #include using namespace std; int main() { int testCase = 10; int len; string str; bool isValid; for (int tc = 1; tc > len >> str; stack st; isValid = true; for (int i = 0; i < len; i++) { // 열린 괄호인 경우 push if(str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '' && st.top() != ' 2021. 3. 1. [SWEA] 3347 올림픽 종목 투표 출처: SWEA Input 2 4 3 5 3 1 4 4 3 2 6 6 3 1 4 1 5 9 2 6 5 3 5 9 Output #1 2 #2 1 A[], B[]를 입력받고, A[1..N]중에서 B[i] 예산내에서 가장 재밌는 종목에 투표하기 투표 결과내에서 가장 많은 투표 받은 종목 번호 출력 #include #include using namespace std; int A[1001], B[1001], sports[1001]; int N, M; int main(){ int testCase; cin >> testCase; for (int tc = 1; tc > N >> M; for (int i = 1; i > A[i]; } for (int i = 1; i > B[i]; } for (int i = 1; i 2021. 3. 1. [SWEA] 1213 String 출처: SWEA Input 1 ti xxxxtixxxti 2 ing aaingaaaain Output #1 2 #2 1 찾고자 하는 문자(pattern) 만큼 문자열에서 차례로 비교하며 일치하는 개수를 찾아냅니다. #include #include using namespace std; int n, k; int answer; int main() { int testCase = 10; string pattern, str; int answer, idx; for (int tc = 1; tc > idx >> pattern >> str; answer = 0; for (int i = 0; i < str.length(); i++) { int idx = i; bool isSame = true; for (int j = 0; .. 2021. 3. 1. [SWEA] 9088 다이아몬드 출처: SWEA Input 2 2 0 1 1 3 3 1 6 4 Output #1 2 #2 2 "선택된 다이아몬드 크기 차이가 K 이하인 것들"을 처리할 때는 선택된 다이아 중 가장 작은 크기와 가장 큰 크기의 차이가 K 이하인 경우를 의미합니다. 계수 정렬과 같이 diamond[]에 다이아몬드 크기별 개수를 저장합니다. left를 기준으로 k 간격만큼 떨어진 지점을 right로 두어서 left와 right 사이의 다이아몬드 개수를 셉니다. 그 중 가장 많이 선택될 수 있는 경우를 출력 #include #include using namespace std; #define MAX 10000 int n, k; int diamond[MAX + 1]; // 0~10000 크기의 다이아몬드 int answer; in.. 2021. 3. 1. [SWEA] 7829 보물왕 태혁 출처: [SWEA] 7829 보물왕 태혁 Input 3 4 2 3 4 6 3 27 3 9 1 13 Output #1 12 #2 81 #3 169 1과 자기자신(=N)을 제외하고 약수들이 주어지므로 약수들의 최솟값과 최댓값을 곱하면 원래의 수가 나옵니다. ▷ 2 3 4 6 → 2 × 6 = 12 ▷ 3 9 27 → 3 × 27 = 81 ▷ 13 → 13 × 13 = 169 * 문제 Input Data를 오름차순으로 정렬해야 합니다. import java.io.*; import java.util.*; public class Solution { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR.. 2021. 3. 1. [SWEA] 4042 Closest 출처: [SWEA] SW 문제해결 심화 - 계산기하학 Input 1 4 0 0 10 10 0 10 10 0 Output #1 100 ※ [BOJ] 5620 가장 가까운 두 점의 거리 풀이 참조 [BOJ] 백준 5620 가장 가까운 두 점의 거리 출처: https://www.acmicpc.net/problem/5620 Input 3 5 5 0 0 -3 -4 Output 25 N의 범위가 충분히 크기 때문에 완전 탐색이나 분할 정복 기법으로는 TLE 발생. Line Sweep 알고리즘을 사용합니다. ※ y 좌.. zoosso.tistory.com - x, y 좌표 범위가 크므로 long으로 표현 - 효율적인 메모리를 위해 Comparable보다 Comparator이용! import java.io.*; imp.. 2021. 3. 1. [SWEA] 4052 프리랜서 출처: [SWEA] SW 문제해결 심화 - 동적 계획법 Input 1 9 10 1 5 30 4 7 25 2 9 42 8 10 9 1 4 20 5 9 27 7 10 16 1 3 15 5 7 7 Output #1 49 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com ex) {T8, T2, T4} = {15 + 25 + 9} = 『49』로 일정이 겹치지 않게 가장 많이 돈을 버는 경우. 구현 먼저, 요청.. 2021. 3. 1. [SWEA] 4043 선 맞춤 출처: [SWEA] SW 문제해결 심화 - 계산기하학 Input 1 4 1 1 2 2 3 3 2 4 -1 Output #1 2 A1 = 1, A2 = 1, An = An-1 + An-2 (n ≥ 3) 피보나치 수열을 구현하는 방법 중 2가지가 있습니다. ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com 구현 ▶ DP[i] = i 번째 점을 포함하며 그 점까지 조건을 만족하는 꺽은 선 중 선분 개수의 .. 2021. 3. 1. 이전 1 2 3 4 5 6 ··· 8 다음 반응형
