본문 바로가기

분류 전체보기

 (340)
[백준 / BOJ] 5052 전화번호 목록 문제 출처 : www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 전화번호 목록을 입력받았을때, 그 목록이 일관성이 있나 없나 구하는 문제다. 예를들어 A = 911 B = 9123 C = 91 1234 를 입력받았을때, C에게 전화할려고 전화번호를 누르면 911을 누르는순간 A에게 전화가 가므로 일관성이없는 목록이다. 풀이 Trie알고리즘을 배우고 풀었는데, 새로운 알고리즘이라기 보다 구조체를 응용하는 느낌이였다. 구조체를 선언하고 그 구조체에 자판 배열을 할당한..
[백준 / BOJ] 1241 머리 톡톡 문제 출처 : www.acmicpc.net/problem/1241 1241번: 머리 톡톡 엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학� www.acmicpc.net N명의 학생이 원형으로 앉아있다. 1번 학생부터 N번 학생까지 순서대로 일어나면서 자신이 쓴 숫자가 다른사람의 숫자의 배수라면 머리를 한대친다. 이때 각학생이 머리를 총 몇번치는지 구하는 문제이다. 풀이 완전탐색으로 풀게되면 100001 * 50000이라 시간초과가 난다. arr배열을 만들어 해당 숫자가 나온 횟수를 저장해주고, 약수가 되는 값의 범위를 찾아 풀었다. i번 학생이 머리에..
[백준 / BOJ] 1105 팔 문제 출처 : www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net L과 R을 입력받았을때, L보다 크거나 같고, R보다 작거나 같은수중 8이 최소한으로 들어가는수를 찾으면된다. 풀이 R의 최댓값이 20억이라 완전탐색으로 찾을려하면 시간초과가 난다. 8의 개수를 찾아야 하는것 이므로 L과 R의 자릿수가 같다면, 앞에서 부터 탐색하며 L과 R의 해당 자릿수가 8로 같을때를 찾아주면된다. 예제의 경우 8808 8880 은 천의자리수와 백의자리수가 모두 8로 같아서 최소한으로 나올수있는 8의 갯수는..
[백준 / BOJ] 14650 걷다보니 신천역 삼 (small) 문제 출처 : www.acmicpc.net/problem/14650 14650번: 걷다보니 신천역 삼 (Small) 욱제는 ‘삼’이란 음절을 참 좋아한다. 인삼, 홍삼, 해삼, 삼성, 이춘삼(李春森), 삼식이, 삼시세끼, ㄴㄴ 그거 안 삼, 삼과 죽음, 알았삼, 금강삼도 식후경, 걷다보니 신천역 삼, 그리고 특히 일�� www.acmicpc.net N을 입력받았을때, 0 , 1 , 2만을 가지고 N자리 3의 배수를 만들어야한다. N = 1 이라면 0 , 1 , 2 로 만들수있는 3의 배수가 없으니 0 출력 N = 2 라면 1 2 2 1 두가지를 만들수있다. (현재 숫자에 더하는게 아니라 숫자를 이어붙이는 형식임에 주의하자) 풀이 완전 탐색 문제다. 3의 배수가 갖는 규칙을 찾는게 중요했는데, 3의 배수라..
[백준 / BOJ] 18679 Banana 문제 출처 : www.acmicpc.net/problem/18679 18679번: Banana The first line of input will contain a single integer N, the number of words in the dictionary (1 ≤ N ≤ 100). The following N lines will each contain a sentence of the format x = y where x is an English word and y is a Minionese word. The next line wil www.acmicpc.net 입력 받은 문자를 미니언 언어로 바꿔서 출력하면된다. 예를들어, I love banana -> mo amo banana 입력에서 각 문자..
[백준 / BOJ] 17349 1루수가 누구야 문제 출처 : www.acmicpc.net/problem/17349 17349번: 1루수가 누구야 (1 2)가 거짓말이라면, 선수 2가 1루수라는 주장과 1루수가 아니라는 주장이 동시에 존재하여 모순이다. (0 4)가 거짓말인 경우도, 마찬가지의 이유로 모순이다. (0 2)가 거짓말인 경우, 선수 2를 유�� www.acmicpc.net 총 9명의 선수중 1루수가 누구인지 찾는 문제이다. 9개의 줄에거쳐 각 선수가 주장을하는데 무조건 한명은 거짓말을 하고있다. 선수들의 주장은 1 A: 선수 A가 1루수이다. 0 A: 선수 A는 1루수가 아니다. 로 나타난다. (단, 1루수를 찾을수 없으면 -1을 출력한다.) 풀이 "한명의 선수가 거짓말을 하고있다." 는 조건이 있으니, 1번 선수가 거짓말을 할때, 2번 ..
[백준 / BOJ] 14746 Closest Pair 문제 출처 : www.acmicpc.net/problem/14746 14746번: Closest Pair Your program is to read from standard input. The input consists of four lines. The first line contains two integers, n (1 ≤ n ≤ 500,000) and m (1 ≤ m ≤ 500,000), where n is the number of points in set P and m is the number of points in set Q. In th www.acmicpc.net 수평선 c1위에있는 점 P들이 있고 (c1, P1) (c1, P2) (c1, P3)... 수평선 c2위에있는 점 Q들이 있다. (c2..
[백준 / BOJ] 1937 욕심쟁이 판다 문제 출처 : www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net N*N크기의 대나무 숲에있는 판다는 한 지역의 대나무를 다 먹으면 상하좌우중 한 방향으로 움직일수있다. 단, 이때 움직인곳은 전 지역보다 대나무가 많아야한다. 풀이 9달전에 풀다가 틀렸었는데, 알고리즘 공부를 더 하고서야 맞췄다. (9달전에는 바텀업 구현을 못해서 풀지 못했음) DFS와 DP를 합친 문제다. 1. (i ~ N) (j ~ N) 까지 전부다 돌려준다. 2. (i,j)점에서 시..

티스토리툴바