본문 바로가기

알고리즘 풀이/백준43

[BOJ] 15898. 피아의 아틀리에 ~신비한 대회의 연금술사~ - JAVA 🔗문제 👨🏻‍💻 풀이 및 코드 문제 유형 및 난이도 : 구현, 브루트 포스 / G1 1. Point 클래스 생성 재료를 회전할 수 있기 때문에, score, color 배열을 따로 만든다면 각각을 회전 시켜야 한다. 한번에 넣어 회전시키기 위해 Class 를 생성했다. static class Point { int score; char color; Point(int score, char color) { this.score = score; this.color = color; } } 2. N개 중에 3개를 뽑아 나열한다. -> 순열 N개 중에 이미 뽑은 재료는 건너뛴다. selection에는 넣어야 할 재료의 번호와 순서를 저장한다. ex) 2, 1, 3 3개의 재료를 모두 뽑았다면, 가마의 상태를 초기화하고.. 2023. 6. 30.
[BOJ] 6987. 월드컵 - JAVA 🔗 문제 👨🏻‍💻 풀이 및 코드 문제 유형 및 난이도 : 브루트포스, 백트랙킹 / G4 나한텐 좀 어려웠다. 처음엔 단순하게 한 개의 팀이 경기를 하는 횟수가 5여야 하고, 진 횟수와 이긴 횟수를 비교하고, 비긴 횟수가 짝수로 떨어지면 될 거라고 생각했는데 다른 사람들 해설을 참고하니 아예 접근 방식이 틀리고 완탐 + 백트랙킹으로 푸는 문제였다. 일단 조건을 찬찬히 살펴보자. 총 6개의 팀이 있다. A, B, C, D, E, F 한 번 경기를 치룬 팀과는 경기를 다시 치루지 않는다. 이 때 치르게 되는 총 경기의 횟수는 얼마일까? A - B, C, D, E, F B - C, D, E, F C - D, E, F D - E, F E - F 이렇게 총 15번 이다. (5 + 4 + 3 + 2 + 1) 이 경우.. 2023. 5. 15.
[BOJ] 17825. 주사위 윷놀이 - JAVA 🔗 문제 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 👨🏻‍💻 풀이 및 코드 문제 유형 및 난이도 : 브루트포스, 시뮬레이션, 백트랙킹 / G2 주의해야 할 점 지름길로 경로를 변경한 후, 그 위치에 다른 말이 있는지 확인할 때 25 → 30 → 35 → 40 경로는 세 지름길에 공통으로 겹치는 길이란걸 체크해야한다. 전체 코드 import java.io.*; import java.util.*; public class Main_bj_17825_주사위윷놀이 { static int ans; static int[.. 2023. 5. 13.
[BOJ] 23290. 마법사 상어와 복제 - JAVA 🔗 문제 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 👨🏻‍💻 풀이 및 코드 문제 유형 및 난이도 : 구현, 시뮬레이션 / G1 풀이 시뮬레이션 문제라서 차근차근 해결하면서 풀었다. 1. 입력 ① 입력으로 들어오는 물고기들의 위치와 방향을 List 에 담는다. class Fish { int x, y;// 위치 int dir;// 방향 } List fishes = new ArrayList(); fishes.add(new Fish(x, y, dir); ② 상어의 위치를 받는다... 2023. 4. 24.
[BOJ] 11660. 구간 합 구하기 5 - JAVA 🔗 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 다이나믹 프로그래밍, 누적 합 2차원 배열에서 시작 지점과 끝 지점 사이의 값들의 합을 구하는 문제 풀이 총 2가지 방법으로 풀었다. 처음에 푼 방법으로 1412ms 가 나왔는데 채점 현황을 보니 900ms 로 푼 사람이 있어서 다른 풀이 방식을 찾아봐서 다시 풀었다. 첫 번째 풀이 방법이 두 번째보다 더 쉽지만 .. 2023. 3. 16.
[BOJ] 10986. 나머지 합 - JAVA 🔗 문제 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 수학, 누적합 주어진 배열 중 구간(i, j) 합 이 M 으로 나누어 떨어져는 구간의 갯수를 구하는 문제 풀이 시간 복잡도 : O (N) 문제를 풀기 앞서, 아래의 모듈러 연산의 분배 법칙을 알고 있어야 한다. 문제에 나와있는 '연속된 부분 구간의 합이 M 으로 나누어 떨어지는' 이라는 의미를 생각해보자. 어떠한 구간 [a, b] 에 대해 '[a, b] 구간합 == [1, b.. 2023. 3. 15.

티스토리툴바