본문 바로가기

BOJ

[BOJ][JAVA] 1074 - Z 문제 출처: https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 문제 설명 전형적인 이분탐색 문제인데, 이런 류의 문제는 처음 만나봐서 헤멨던 문제입니다. 직관적으로 떠오르는 풀이법인 2차원 배열로 풀었을 경우, 배열의 사이즈가 2의 30제곱까지 올라가기 때문에 무조건 메모리 초과가 일어납니다. 그렇기 때문에 반드시 이분탐색으로 풀어야 하며, 찾아야 하는 r,c좌표가 어느 사분면에 있는지를 알아낸 다음 그 전 사분면들은 값만 더해줄 뿐 더 .. 더보기
[BOJ][JAVA] 2839 - 설탕 배달 문제 출처 : https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 설명 코드 자체는 굉장히 간단한 편인데, 아이디어를 얻기가 그만큼 쉽지는 않았던 문제였습니다. 전형적인 그리디 유형의 문제로, 5kg으로 최대한 많이 들고 가도록 하는게 포인트입니다. 5로 나눠지면 5kg로 다 들고갈 수 있다는 뜻이니 그 전에 구한 3kg의 갯수와, 남은 설탕을 5로 나눈 몫을 더해서 답을 내고 그렇지 않다면 3kg의 갯수를 하나씩 늘려줍니다. 계속 3kg로만 담아지다 .. 더보기
[BOJ][JAVA] 15686 - 치킨 배달 문제 출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 설명 최대 M개를 고른다는 말에 처음에 부분집합으로 풀었는데, 답이 나오지 않았습니다. 생각해보니 M개보다 적게 고르든 M개만큼 고르든, 어쨌든 치킨 거리는 최솟값으로 계산되기 때문에 결과값은 동일하다는 결론이 나왔고, 그래서 M개만을 뽑는 조합으로 풀었더니 정답이 나왔습니다. 치킨집과 집을 각각 ArrayList에 따로 저장하고, 치킨집의 전체 개수 중 .. 더보기
[BOJ][JAVA] 3040 - 백설 공주와 일곱 난쟁이 문제 출처 : https://www.acmicpc.net/problem/3040 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 문제 설명 백설 공주는 공주가 되기 전에 유명한 수학자였다니ㅋㅋㅋㅋ설명이 재미있는 문제였습니다ㅎㅎ 문제에도 나와 있듯 한 마디로, 아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾는 문제이기때문에, 조합으로 비교적 쉽게 풀 수 있는 문제였습니다:) 코드 import java.util.Scanner; //조합 public class BOJ3040_SnowWhite { .. 더보기
[BOJ][JAVA]2493 - 탑 문제 출처 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 설명 이 문제는 스택을 사용해서 푸는게 핵심입니다. 문제를 보고 바로 스택을 써야 한다는 감이 오지는 않았고, 수업에서 풀이를 듣고서야 그렇게 풀어야 함을 알게 되었습니다. 완전 탐색 등으로 나이브하게 풀면 바로 시간초과나 메모리 초과가 나기 때문에, 스택으로 풀어야만 하는 문제였습니다. 원리는 다음과 같습니다. 만약 스택의 top에 들어있는 탑의 높이가 현재 넣으려고 하는 .. 더보기
[BOJ][JAVA]17478번 - 재귀함수가 뭔가요? 문제출처 : https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제 설명 문제 이름에서 보여주듯, 재귀함수를 적절히 구현하는 문제입니다. 처음에 반복구간을 잘못 나눠서 "라고 답변하였지." 이 부분이 한번 적게 나와서, 꽤 헤맸던 문제였습니다ㅠ 그리고 '____'이 추가되는 부분은 반복문을 돌리는게 아니라, 그냥 간단하게 string에 계속 더해주며 인자로 넘겨 처리하는 것도 포인트입니다. 또, 텍스트 내용을 정확히 코드에 넣으셔야지 출력으로 .. 더보기
[BOJ][JAVA]1244 - 스위치 켜고 끄기 문제 출처 : https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 문제 설명 조건이 많지만 로직 자체는 복잡하지 않아서, 그 조건을 하나씩 구현하기만 하면 되는 문제였습니다. 다만 bit flip시킬 때마다 조건문을 반복적으로 쓰지 않고, 삼항 연산자만으로 간단하게 표현이 가능하다는 게 포인트였습니다. 코드 //기억할 것 : bit flip 으로 " ? : " 연산자 활용 가능! import java.util.Scanner; public cl.. 더보기
[BOJ][JAVA]2961 - 도영이가 만든 맛있는 음식 문제 출처 : https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 문제: Point : 부분집합 코드: import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2961_TastyFood { static int[] sour; static int[] bitter; static int.. 더보기

티스토리툴바