본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 17281 ⚾ 출처: https://www.acmicpc.net/problem/17281 Input 2 4 3 2 1 0 4 3 2 1 1 2 3 4 1 2 3 4 0 Output 46 야구 규칙 - 한 이닝에 3아웃이 발생하면 이닝 종료. - 경기 시작 전 정해진 타순으로 게임 진행(교체 x) 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않으면 이닝이 끝나지 않고, 1번 타자부터 다시 타석에 선다. + 9명 중 아웃을 하는 사람이 적어도 한 명이 있으므로 이닝은 종료됨. - 팀의 수비나 실점은 고려하지 않는다. - 타순은 이닝이 변경되어도 순서 유지 ex) 2이닝에 6번타자가 마지막이라면, 3이닝은 7번 타자부터 타석에 선다. - 공격은 1루, 2루, 3루, 홈에 도착해서 1점을 득점하는 방식. - 주자는 1루, 2.. 2021. 2. 22.
[BOJ] 백준 1764 듣보잡 출처: https://www.acmicpc.net/problem/1764 Input 3 4 ohhenrie charlie baesangwook obama baesangwook ohhenrie clinton Output 2 baesangwook ohhenrie 원소의 중복 여부를 파악하기 위해 contain() 함수를 이용했지만 시간 제한을 만족 못함. Map을 이용해 『key : value』 중복 여부 처리 ▶ [해시] Hash란? [해시] Hash란? Hash란? 원소가 저장되는 위치가 원소 값에 의해 결정되는 자료구조 - 평균 상수 시간에 삽입, 검색, 삭제가 가능하다. - 매우 빠른 응답을 요구하는 상황에 유용 (Hash는 최소(최대) 원소를 찾는 것 zoosso.tistory.com import .. 2021. 2. 22.
[BOJ] 백준 17070 파이프 옮기기 1 출처: https://www.acmicpc.net/problem/17070 Input 6 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Output 13 파이프pipe 종류 * 종류마다 이동 방법이 다르다. ① 『 → 』 의 경우, 2가지 ② 『 ↓ 』 의 경우, 2가지 ③ 『 ↘ 』 의 경우, 2가지 - Pipe의 끝지점 경로 고려. - Pipe 상태에 따른 경로를 고려하면 아래의 범위에서 움직인다. 가로, 세로 방향은 다음 끝지점이 벽이지만 확인하면 되지만 대각선의 경우에는 3 군데를 확인해야 한다. ※ Pipe 이동이 처음부터 불가능하다. Input 5 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .. 2021. 2. 22.
[BOJ] 백준 17136 색종이 붙이기 출처: https://www.acmicpc.net/problem/17136 Input 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 Output 9 5가지 종류의 색종이로 10 x 10 종이 위에 『 1 』을 색종이 최소 개수로 덮는 문제입니다. ※ 색종이 종류: 1×1, 2×2, 3×3, 4×4, 5×5 - 『 0 』인 부분을 덮어서는 안됩니다. - 색종이가 겹쳐서는 안됩니다. Greedy 방식으.. 2021. 2. 22.
[BOJ] 백준 10814 나이순 정렬 출처: https://www.acmicpc.net/problem/10814 Input 3 21 Junkyu 21 Dohyun 20 Sunyoung Output 20 Sunyoung 21 Junkyu 21 Dohyun 회원을 나이 순, 나이가 같으면 가입한 순 정렬하는 문제입니다. 우선순위 큐를 이용하여 처리. import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = Integer.parseInt(sc.next()); PriorityQueue pq = new Priority.. 2021. 2. 22.
[BOJ] 백준 1708 블록 껍질 출처: https://www.acmicpc.net/problem/1708 Input 8 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 Output 5 블록 껍질(Convex Hull) 구현하는 문제 블록 껍질(Convex Hull) Cunvex Hull(블록 껍질)은 2차원 평면상에 여러개의 점이 있을 때, 그 점들 중에서 일부를 이용하여 볼록 다각형을 만들되, 볼록 다각형 내부에 사용하지 않은 모든 점을 포함시키는 것을 의미합니 zoosso.tistory.com ① 기준점(first) 설정 ← 일반적으로 y 좌표가 가장 작은 것. (가장 작은 y 좌표값이 2개 이상이라면 x 좌표 값이 작은 것 ) ② 기준점(first)을 중심으로 각도순 정렬 - CCW(반시계 방향), 일직선상 거리 비교 ※.. 2021. 2. 22.
[BOJ] 백준 17135 캐슬 디펜스 출처: https://www.acmicpc.net/problem/17135 Input 6 5 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 0 Output 9 - 궁수의 위치는 끝 행 + 1에 위치하며 3명이 배치됩니다. (각 칸의 궁수는 최대 1명 배치) 턴의 진행 방식 - 3명의 궁수는 동시에 가장 가까운 거리의 적 1명을 공격 - 공격할 수 있는 거리는 D 이하. 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2| - 가장 가까운 거리의 적이 여러명인 경우 가장 왼쪽에 있는 적을 공격 - 적은 여러명의 궁수들로부터 공격될 수 있습니다. - 공격 받은 적은 게임에서 제외 - 궁수의 공격이 끝나면 살아남은 적이.. 2021. 2. 22.
[BOJ] 백준 4355 서로소 출처: https://www.acmicpc.net/problem/4355 Input 7 12 0 Output 6 4 오일러 피(파이) 함수 ϕ(n)를 이용합니다. 오일러 피(파이) 함수(Euler's phi function) 오일러 피(파이) 함수 ϕ(n) 1~n까지의 수 중에서 n과 서로소인 수의 갯수 ※ 서로소 관계: 두 수 a, b의 공약수가 1뿐인 두 정수를 의미한다. ϕ(1) = 1 (1은 1과 서로소) ϕ(8) = { 1, 3, 5, 7 } =.. zoosso.tistory.com import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamRead.. 2021. 2. 22.
[BOJ] 백준 17406 배열 돌리기 4 출처: https://www.acmicpc.net/problem/17406 Input 5 6 2 1 2 3 2 5 6 3 8 7 2 1 3 8 2 3 1 4 5 3 4 5 1 1 1 9 3 2 1 4 3 3 4 2 4 2 1 Output 12 회전 연산] 6 x 6 배열과 (r, c, s) = (3, 4, 2) 일 때, 좌측 상단: (r-s, c-s) / 우측 하단: (r+s, c+s) 『배열 A의 값』은 각 행에 있는 모든 수의 합 중 최솟값을 의미. 주어진 회전을 순서로 임의로 배정했을 때, 『배열 A의 값』 중 최소값을 구하는 문제입니다. 구현 순서 ① 모든 회전 가능한 회전 경우의 수 구현 ← 순열 ② 회전 순서가 정해지면 배열 내부에서 특정 영역(정사각형)에 대한 회전(재배치) 회전(재배치)을 .. 2021. 2. 22.
[BOJ] 백준 1786 찾기 출처: https://www.acmicpc.net/problem/1786 Approach [문자열] KMP 알고리즘을 이용하여 해결할 수 있다. [문자열] KMP 알고리즘 KMP 알고리즘이란? 『KMP 알고리즘』 문자열을 검색할 때, 불필요한 반복을 줄이기 위해 검색 문자열의 접두사와 접미사의 중복 길이를 이용한 알고리즘 입니다. (※ Knuth–Morris–Pratt algorithm, KMP) zoosso.tistory.com import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWrit.. 2021. 2. 22.
반응형

티스토리툴바