본문 바로가기

알고리즘 풀이56

[프로그래머스] 당구 연습 - JAVA 🔗 문제 👨🏻‍💻 풀이 및 코드 이 문제를 해결하기 위해선 한 가지 수학적 아이디어가 필요합니다. 입사각과 반사각이 같은 경우는 다음과 같이 네 방향으로 공을 대칭 이동 할 수 있습니다. 예를 들어, 빨간 타겟공을 1번 위치로 대칭이동을 한다면, 파란 시작 공과 1번 공과의 거리가 시작 공에서 벽을 맞고 빨간 공으로 돌아온 거리와 같기 때문에 해당 거리가 최단 거리 입니다. 즉, 네 방향으로 대칭 이동 시킨 후, 그 중 시작 공과의 거리가 가장 짧은 값을 리턴하면 됩니다. 단, 주의할 점이 있습니다. 예시와 같이 3번 방향으로 대칭 이동을 시키는 경우 벽에 맞기 전에 타겟 공을 먼저 맞기 때문에 이와 같이 일직선으로 놓인 방향은 제외시켜야 합니다. 대칭 이동하는 공의 좌표를 수식으로 바꾸면 다음과 같습니.. 2023. 6. 28.
[프로그래머스] 방의 개수 - JAVA 🔗 문제 👨🏻‍💻 풀이 및 코드 접근 방법 사방이 막힌 도형이 만들어지는 조건은 이미 한번 방문한 점을 다시 방문한다면 도형이 만들어진다. 그림에서 빨간색 점을 방문했던 점이라고 한다면 마지막 빨간색 선, 즉 방문했던 점을 다시 방문했을 때 도형이 만들어진다. 단, 이미 그어진 선을 다시 잇는 경우는 안된다. 즉, 이미 이어진 선인지 체크해야 한다. 추가로 주의해야할 점은 대각선 체크를 위해 이동할 때 두 칸씩 이동해야 한다. 해당 그림처럼 이동했다면 삼각형이 하나 만들어지지만 위의 접근방식으론 갯수를 셀 수 없다. 같은 이동을 두 칸씩으로 바꾸면 대각선 경우의 도형의 갯수도 셀 수 있다. 정리 입력에서 주어진 방향대로 점을 이동시키면서, 이미 방문했던 점이고 처음 잇는 선이라면 도형의 갯수를 증가시킨다.. 2023. 6. 8.
[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.
[프로그래머스] Level 2. 두 원 사이의 정수 쌍 🔗 문제 👨🏻‍💻 풀이 및 코드 원에 포함된 정수 쌍의 갯수는 x^2 + y^2 = r^2 공식을 사용해 구할 수 있다. ex) 예제에 나온 r = 3 일 때의 정수 쌍의 갯수 x 가 1일 때, y 는 2루트2다. → 2.xx 따라서 y의 정수의 갯수는 0, 1, 2 (3개) x 가 2일 때, y 는 루트5다. → 2.xx 따라서 y의 정수의 갯수는 0, 1, 2 (3개) x 가 3일 때, y 는 0 이다. 따라서 y의 정수의 갯수는 0 (1개) 이제 원에 포함된 정수 쌍의 갯수를 구하는 법을 알았으니, 두 원 사이에 포함된 정수 쌍의 갯수를 구하려면 바깥 원에 포함된 정수 쌍의 갯수 - 안쪽 원에 포함된 정수 쌍의 갯수를 하면 된다. 주의해야 할 점이 정수 쌍의 갯수를 셀 경우, 안쪽 원의 테두리에 있.. 2023. 5. 12.
[프로그래머스] Level 2. 요격연습 - JAVA 🔗 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨🏻‍💻 풀이 및 코드 문제 유형 및 난이도 : 그리디 / Level 2 풀이 미사일을 시작 순으로 정렬하는 방법과 끝나는 시점 순으로 정렬하는 방법 2가지로 풀었다. 전체 코드 Sol1) import java.util.*; class Solution { public int solution(int[][] targets) { Arrays.sort(targets, (o1, o2) -> (o1[0] - o2[0])); // s 오름차순으로 정렬 int cnt = 0; int last = -1; // 커버할.. 2023. 4. 27.

티스토리툴바