백준 14315번
https://www.acmicpc.net/problem/14315

Google Coding Practice with Kick Start Session #2 - Kick Start 2022
https://codingcompetitions.withgoogle.com/kickstart/round/00000000008f4a94/0000000000b5496b

문제

---

Sherlock and Watson have recently enrolled in a computer programming course. Today, the tutor taught them about the balanced parentheses problem. A string S consisting only of characters ( and/or ) is balanced if:

• It is the empty string, or:
• It has the form (S), where S is a balanced string, or:
• It has the form S1S2, where S1 is a balanced string and S2 is a balanced string.

Sherlock coded up the solution very quickly and started bragging about how good he is, so Watson gave him a problem to test his knowledge. He asked Sherlock to generate a string S of L + R characters, in which there are a total of L left parentheses ( and a total of R right parentheses ). Moreover, the string must have as many different balanced non-empty substrings as possible. (Two substrings are considered different as long as they start or end at different indexes of the string, even if their content happens to be the same). Note that S itself does not have to be balanced.

Sherlock is sure that once he knows the maximum possible number of balanced non-empty substrings, he will be able to solve the problem. Can you help him find that maximum number?

생각하기

---

• 조합을 구하는 공식을 찾으면 된다.
• n의 총 합 식을 사용하면 된다 -> (n + (n-1)) / 2
• 14314의 small 버전도 있는데, 그냥 long과 int의 자료형 차이이다.
• 구글 킥스타트 <Coding Practice with Kick Start Session #2 - Kick Start 2022> 에도 나온 문제이다.

동작

처음에 문제가 영어라서 이해를 잘못하고 combination으로 푸는 문제라고 생각하고 factorial메소드까지 따로 만들면서 했었는데,

n = Math.min(L, R)로 작은 값을 찾아서 n * ((n + 1) / 2) 의 공식을 활용하면 쉽게 풀 수 있는 문제였다.

식이 잘 이해 안되시는 분들을 위해서 참고 링크를 올립니당
https://sseong40.tistory.com/9

코드

---

Java

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for(int i=0; i<T; i++) {
			sb.append("Case #").append(i+1).append(": ");
			StringTokenizer st = new StringTokenizer(br.readLine());
			long result = Math.min(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			result = result * (result + 1) / 2;
			sb.append(result).append('\n');
		}
		bw.write(sb.toString()); bw.flush(); bw.close();
	} // End of main
} // End of Main class

Kotlin

import java.util.*
import java.io.*

fun main() {
        val br = BufferedReader(InputStreamReader(System.`in`))
        val bw = BufferedWriter(OutputStreamWriter(System.`out`))
        val sb = StringBuilder()
        val T = br.readLine().toInt()
        for(i in 0 until T) {
                sb.append("Case #").append(i+1).append(": ")
                var st = StringTokenizer(br.readLine())
                var L = st.nextToken().toLong()
                var R = st.nextToken().toLong()
                var min = Math.min(L, R)
                var result = (min * (min + 1) / 2)
                sb.append(result).append('\n')
        }
        bw.write(sb.toString());bw.flush();bw.close()
} // End of main