자바/알고리즘 문제 풀이79

★ 백준/1149 RGB거리 / 다이나믹 프로그래밍 ,메모이제이션 RGB거리 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 128 MB 88412 46869 34983 52.386% 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진.. 자바/알고리즘 문제 풀이 2022. 12. 19.

★ 백준/1912 연속합 / 다이나믹 프로그래밍,메모이제이션 연속합 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) 128 MB 114189 40905 28810 34.544% 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 출력 첫째 줄에 답을 출력.. 자바/알고리즘 문제 풀이 2022. 12. 19.

백준/9461 파도반 수열 / 다이나믹프로그래밍 + 제출전 최악의경우 체크해보기 파도반 수열 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 76537 33556 27488 42.495% 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이.. 자바/알고리즘 문제 풀이 2022. 12. 16.

백준/1904 01타일 / 다이나믹 프로그래밍 + 제출전 최악의경우값들 넣어보기 + dp배열의 크기는 나올수있는 최대값으로 잡기 01타일 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.75 초 (추가 시간 없음) 256 MB 75477 24571 19491 31.851% 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, .. 자바/알고리즘 문제 풀이 2022. 12. 16.

백준/14889 스타트와 링크 / 조합 = dfs + 백트래킹 스타트와 링크 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 72451 35877 21057 46.362% 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은.. 자바/알고리즘 문제 풀이 2022. 12. 16.

백준/14888 연산자 끼워넣기 /dfs + 백트래킹 / 완전탐색(브루트포스) 연산자 끼워넣기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 74842 39010 24835 49.319% 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같.. 자바/알고리즘 문제 풀이 2022. 12. 15.

백준/15651 N과 M (3) // 중복 순열 N과 M (3) 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 46848 31120 23601 66.711% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 예제 출력 1 복사 1 2 3 예제 입력 2 복사 4 2 예제 출력 2 복사 1 .. 자바/알고리즘 문제 풀이 2022. 12. 15.

백준/15649 N과 M(1) // 순열 N과 M (1) 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 72866 45638 30107 61.833% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 예제 입력 1 복사 3 1 예제 출력 1 복사 1 2 3 예제 입력 2 복사 4 2 예제 출력 2 복사 1 2 1 3 1 4 2 1.. 자바/알고리즘 문제 풀이 2022. 12. 15.

백준/1676 팩토리얼 0의 개수 // BigInteger , 0의개수 규칙 팩토리얼 0의 개수 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 52448 25204 20824 47.857% 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 복사 10 예제 출력 1 복사 2 예제 입력 2 복사 3 예제 출력 2 복사 0 풀이 //팩토리얼 문제 , 팩토리얼은 상당히 큰수를 만들게된다. //여기서는 n이 최대 500이다. 500!는 상상도 못할 큰수일것이다. 팩토리얼 계산사이트에 500!를 입력해보니 너무큰숫자이다. //이 숫자는 int이든 long이든 담을 수 없다. //그럴때 사용하는것이 .. 자바/알고리즘 문제 풀이 2022. 12. 15.

백준/9375 패션왕 신해빈 // 조합 , 경우의 수 패션왕 신해빈 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 24592 13453 11559 54.863% 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되.. 자바/알고리즘 문제 풀이 2022. 12. 15.

백준/1010 다리놓기 // 파스칼 삼각형 + 다이나믹프로그래밍 다리 놓기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.5 초 (추가 시간 없음) 128 MB 64625 29963 24502 48.438% 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원.. 자바/알고리즘 문제 풀이 2022. 12. 15.

★백준/11051 이항 계수 2 /조합,BigInteger,파스칼의 삼각형 이항 계수 2 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 48877 18134 14257 37.642% 문제 자연수 N\(N\)과 정수 K\(K\)가 주어졌을 때 이항 계수 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 1,000, 0 ≤ K\(K\) ≤ N\(N\)) 출력 (NK)\(\binom{N}{K}\)를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 복사 5 2 예제 출력 1 복사 10 풀이 이항계수1 도 조합으로 풀어서 조합으로 하려니까 조합의 시간복잡도는 O(2^n)이라서 시간초과에 걸릴것 같았다. 그래서 위와 같은 조합공식을.. 자바/알고리즘 문제 풀이 2022. 12. 14.

이전 1 2 3 4 5 6 7 다음

티스토리툴바