Baekjoon

[15990] 1, 2, 3 더하기 5(C++)

문제 바로가기 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다. 1+2+1 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 🌱 해결 방법 [9095] 1, 2, 3, 더하기의 응용 버전 [9095] 1, 2, 3 더하..

[16194] 카드 구매하기2

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 📌 해결 방법 [11052] 카드 구매하기와 매우매우 유사한 문제다. 거의 똑같은 수준...? 풀이 과정도 위의 문제랑 똑같이 생각하면 된다! 상세 내용은 아래 링크 참고 https://aerimforest.tistory.com/111 [11052] 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 ..

[9095] 1, 2, 3 더하기(Top-down & Bottop-up)

문제 [9095] 1, 2, 3 더하기 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 해결 방법 정수 4를 1, 2, 3의 합으로 나타낼 수 있는 모든 경우의 수를 1로 시작하는 경우 2로 시작하는 경우 3으로 시작하는 경우 ..

[11725] 트리의 부모 찾기(C++)

문제 [11725] 트리의 부모 찾기 해결 방법 이 문제도 전형적인 dfs, bfs 문제이다. 한 가지, 현재 노드의 부모 노드가 몇번인지 저장할 배열만 추가하면 된다. 나는 인접리스를 활용한 dfs로 구현하였는데, 인접한 노드를 모두 입력받은 후 리스트의 형태는 아래와 같다. 노드 1 6 4 2 4 3 6 5 4 1 2 7 5 3 6 1 3 7 4 1번 노드부터 탐색을 시작하는데, 1번 노드와 연결된 노드는 무조건 1번 노드의 자식임을 알아두자. 또한, 나와 연결된 노드는 나의 부모이거나 자식이거나 둘중 하나임을 기억하자. 탐색을 하면서 나와 연결되어있지만 이미 방문한 노드는 부모노드이고, 그렇지 않은 노드는 부모 노드가 아니기에 자식노드로 판단하고 부모로 저장해주면 된다! 내 코드(C++) // [1..

[1049] 기타줄

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 🔎 해결 방법 정렬을 한 후 제일 첫번째 원소를 취하던지, 아니면 입력받을 때마다 비교를 하던지 해서 패키지 가격의 최솟값과 낱개 가격의 최솟값을 찾아야 한다. 그리고 이 두 개의 값만 사용하면 문제를 풀 수 있다! 1. 모두 낱개로 사는게 제일 싼 경우 예를 들어 가장 싼 패키지 가격이 24, 가장 싼 낱개의 가격이 3이라면 항상 낱개로 사는 것이 더 이득이다. 따라서 (가장 싼 낱개 가격)..

[2437] 저울(C++)

🎅🏻 문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 🧣 해결 방법 예를 들어 추의 무게가 (3, 1, 6, 2, 7, 30, 1) 이렇게 주어졌다면 오름차순 정렬을 하고 처음부터 각 인덱스까지의 추의 무게를 합한 sum 은 아래의 표와 같다. sum = 처음부터 각 인덱스까지의 추의 무게의 합 즉, sum에 저장된 값에 해당하는 무게까지는 우리가 만들 수 있다는 뜻이 된다. ex) sum = 7이면 무게가 1인 것부터 7인 것까지 모두 만들 수 있다는 뜻 i가 4일때부터 한번 차근차근 봐보자. 1) i = 4,..

[1309] 동물원

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 💧 해결 방법 N이 1일 때, 2일 때, 3일 때, 4일 때.... 를 차근차근 계산해보면 규칙성을 바로 발견할 수 있다. dp[i] = 2(가로) * i(세로) 크기의 동물원에 사자를 배치하는 방법의 수 라고 한다면 dp[0] = 1 dp[1] = 3 dp[2] = 7 dp[3] = 20 dp[4] = 41 . . . 즉, 아래와 같은 점화식이 성립하는 것을 알 수 있다. dp[i] = dp[i - 1]*2 + dp[i - 2] ☂️ 내 코드 // [1309] 동물원 // https://www.acmicpc.net/problem/1309 // dp #include int main(void) {..

[1157] 단어 공부

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net alpha 배열을 초기화해줘야 한다는 것은 생각도 못하고 엄한 것만 고치다가 오답률만 더 늘어버렸다. ㅎㅎ 항상 변수 선언하면 초기화부터 하고 사용하자... 한 가지 주의해야 할 점❗️ 문자를 알파벳으로 출력하고 싶은 경우 printf 함수를 쓰면 "%c"로 출력만 해주면 되지만 cout으로 출력하는 경우에는 출력문에서 타입 변환을 할 수 없기 때문에 사전에 원하는 타입으로 선언한 변수에 값을 저장해서 형 변환을 해준 뒤에 출력해..