본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 4153 직각삼각형 출처: https://www.acmicpc.net/problem/4153 Input 6 8 10 25 52 60 5 12 13 0 0 0 Output right wrong right 피타고라스 정리 이용. ▶ a^2 + b^2 = c^2 #include #include #include using namespace std; vector vec; int temp; int main(){ while(1){ vec.clear(); for(int i=0; i> temp; vec.push_back(temp); } // 입력받은 세 변의 길이가 모두 0인 경우 종료 if(vec[0] + vec[1] + vec[2] == 0) break; sort(vec.begin(), vec.end() ); cout 2021. 2. 20.
[BOJ] 백준 6443 애너그램 출처: https://www.acmicpc.net/problem/6443 Input 2 abc acba Output abc acb bac bca cab cba aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa 중복을 제거해서 순열을 구하는 문제입니다. DFS 이용한 코드 #include #include using namespace std; int N, len, alphabet[26]; string str; char output[1001]; void DFS(int idx, int depth) { if (depth == len) { cout > N; while(N--){ for (int i = 0; i < 26; i++) alphabet[i] = 0;.. 2021. 2. 20.
[BOJ] 백준 2456 나는 학급회장이다. 출처: https://www.acmicpc.net/problem/2456 Input 6 3 1 2 2 3 1 3 1 2 1 2 3 3 1 2 1 2 3 Output 1 13 point[1~4] = {1점, 2점, 3점, 합산} 저장 합산 → 3점 → 2점 → 1점 순으로 비교하여 한명이 선정되는지 확인합니다. #define _CRT_SECURE_NO_WARNINGS #include struct Student { // 1~3점 받은 횟수, [4]: 점수 합산 int point[5]; }students[4]; int player[4] = { 0, 1, 1, 1 }; int checkPlayer(int pivot) { int i, value = 0; // 살아남은 학생들 중에서 점수의 최대값 구하기 for (.. 2021. 2. 20.
[BOJ] 백준 1395 스위치 출처: https://www.acmicpc.net/problem/1395 Input 4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4 Output 1 2 ▶ 구간합을 가지는 세그먼트 트리 + Lazy Propagation을 이용 lazy[] = 반전시켜야 하는 횟수 짝수인 경우는 반전시켜보아야 ON 상태의 스위치 개수에는 변화가 없기 때문에 홀수인 경우만 처리합니다. (if. 단말 노드의 ON/OFF 상태를 구해야하는 문제인 경우 변형 필요) tree[]에서 스위치 ON 상태의 개수는 구간의 합 세그먼트 트리를 이용합니다. (단말 노드에는 『0』 과 『1』 이 저장) ex) 특정 노드(구간)의 단말 노드(leaf node) 개수 = e - s + 1 → 반전시 상태가 변하는 스위치 개수 = e.. 2021. 2. 19.
[BOJ] 백준 2573 빙산 출처: https://www.acmicpc.net/problem/2573 Input 5 7 0 0 0 0 0 0 0 0 2 4 5 3 0 0 0 3 0 2 5 2 0 0 7 6 2 4 0 0 0 0 0 0 0 0 0 Output 2 ① map[][]을 순회하며 빙산이 있는 곳을 시작점으로 DFS 탐색하며 연결된 모든 빙산을 탐색합니다. ② 빙산들을 DFS 탐색하면서 바다에 둘러싸인 개수(동서남북)를 확인 후 빙산의 높이를 갱신합니다. ③ 모든 빙산이 녹을 때까지 반복되며, 중간에 빙산이 두 덩어리 이상으로 분리되면 종료 #include const int MAX_NM = 300 + 10; const int dx[] = { 1, -1, 0, 0 }; const int dy[] = { 0, 0, 1, -1 }.. 2021. 2. 18.
[BOJ] 백준 6593 상범 빌딩 출처: https://www.acmicpc.net/problem/6593 Input 3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0 Output Escaped in 11 minute(s). Trapped! - 전형적인 (2차원) BFS 문제에서 3차원으로 확장한 문제입니다. - map과 visited를 [층 h][행 x][열 y]로 표시해서 3중 for문을 이용해서 입력을 받습니다. - BFS 탐색시에는 범위 초과(높이, 행, 열), 벽을 만난 경우, 보다 좋은 비용이 아닌 경우를 제외하고 탐색합니다. ※ Test Case가 존재하므로 초기화에 유의 #include inl.. 2021. 2. 18.
[BOJ] 백준 15552 빠른 A+B 출처: https://www.acmicpc.net/problem/15552 Java에서 빠른 입출력을 보장받기 위해 BufferedoutputStream 이용 [예제] Java 입출력 속도 비교 [BOJ] 백준 15552 빠른 A+B 출처: https://www.acmicpc.net/problem/15552 Input 5 1 1 12 34 5 500 40 60 1000 1000 Output 2 46 505 100 2000 Java에서 빠른 입출력을 보장받기 위해 BufferedoutputStre.. zoosso.tistory.com import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import .. 2021. 2. 18.
[BOJ] 백준 2447 별찍기 - 10 출처: https://www.acmicpc.net/problem/2447 Approach 규칙적으로 형성되는 모양에서 왼쪽 상단의 꼭지점을 시작점으로 잡는다. 최소 크기를 n = 3으로 잡아 좌측 상단 시작점에서부터 재귀적으로 별 모양 형성 ▶ [문제] BOJ 별 찍기 시리즈 [문제] BOJ 별 찍기 시리즈 [BOJ] 2438 별 찍기 - 1 [BOJ] 2439 별 찍기 - 2 [BOJ] 2440 별 찍기 - 3 [BOJ] 2441 별 찍기 - 4 [BOJ] 2442 별 찍기 - 5 [BOJ] 2443 별 찍기 - 6 [BOJ] 2444 별 찍기 - 7 [BOJ] 2445 별 찍기 - 8 [BOJ] 2446 별.. zoosso.tistory.com import java.util.ArrayList; imp.. 2021. 2. 18.
[BOJ] 백준 2448 별찍기 - 11 출처: https://www.acmicpc.net/problem/2448 Approach n이 주어졌을 때, 아래와 같은 별 모양을 형성하는 문제이다. 해당 문제는 다음과 같이 접근해보았다. 재귀적으로 아래의 각 삼각형 상단 좌표를 기준으로 해서 별모양을 형성 : (1) - (2) - (3) - [4] ※ Test Case 통과를 위해서는 아래사항을 주의. 1. null문자는 단 한개도 출력해서는 안된다. 일부 환경 (예: 비주얼 스튜디오)에서는 널 문자가 마치 공백처럼 출력되어 눈에 보이지 않지만, 널 문자와 공백은 엄연히 다르며, 채점 프로그램은 단 한 개의 널 문자라도 발견되면 무조건 오답으로 처리 공백은 무조건 공백 문자 ' ' 띄워쓰기를 이용해 출력. 2. 출력 예제를 드래그해보면 모든 줄은 같.. 2021. 2. 18.
[BOJ] 백준 1003 피보나치 함수 출처: https://www.acmicpc.net/problem/1003 Input 3 0 1 3 Output 1 0 0 1 1 2 재귀를 이용하는 경우 시간 초과나기 때문에 반복문을 이용하여 구현 [수학] 피보나치 수열 구현 (재귀, DP) 피보나치 수열(Fibonacci Numbers)이란? 1 → 1 → 2 → 3 → 5 → 8 → 13 → 21 → 34 → 55 → 89 → 144 → 233 점화식으로 표현하면 다음과 같다. 이를 구현하는 방법은 크게 다.. zoosso.tistory.com [문제 풀이] (0호출, 1호출)을 분석해보면 N=0 일 때, (1, 0) / N=1 일 때, (0, 1)까지를 기본(base)항으로 둔다. 다음항부터 (1, 1) → (1, 2) → (2, 3) → (3, .. 2021. 2. 18.
반응형

티스토리툴바